将字符串划分为含多数字符的子串：DP解法优化求助

若字符串中超过半数位置的字符相同，则该字符串存在多数字符。例如，ababa的多数字符为a（5个位置中有3个），但abab和abcd不存在多数字符。
任何非空字符串都可划分为一个或多个含多数字符的子串，最坏情况下可划分为单个字符的子串。
给定长度≤5000的非空字符串，求可将其划分成含多数字符子串的最小数量。
示例：字符串abca的答案为4（a、b、c、a）；ababa的答案为1（ababa）；aaaabbbcd的答案为2（aaaa、bbbcd）。

我已用动态规划写出一个解法，思路基本正确，但速度过慢：时间复杂度为O(n³)，而字符串长度最高可达5000。请问如何优化？是否需要彻底改变思路？

原O(n³)复杂度代码 #

func minSubstrings(_ s: String) -> Int {
  let chars = Array(s)
  let length = chars.count
  guard length > 0 else { return 0 }

  var dp = Array(repeating: Int.max, count: length + 1)
  dp[0] = 0

  func isValidSubstring(start: Int, end: Int) -> Bool {
    var freq: [Character: Int] = [:]
    for i in start..<end {
      let char = chars[i]
      freq[char, default: 0] += 1
    }
    let substringLength = end - start
    for count in freq.values {
      if count > substringLength / 2 {
        return true
      }
    }
    return false
  }

  for end in 1...length {
    for start in 0..<end {
      if isValidSubstring(start: start, end: end) {
        dp[end] = min(dp[end], dp[start] + 1)
      }
    }
  }

  return dp[length]
}

优化后O(n²)复杂度解法 #

无需彻底改变动态规划思路，只需优化子串合法性的判断逻辑：将原本每次单独统计子串频率的O(n)操作，改为在遍历end指针时逐步维护频率统计，从而将整体复杂度从O(n³)降至O(n²)，完全适配长度5000的字符串。

优化后的代码：

func minSubstrings(_ s: String) -> Int {
  let chars = Array(s)
  let length = chars.count
  guard length > 0 else { return 0 }
  
  var dp = Array(repeating: Int.max, count: length + 1)
  dp[0] = 0
  
  for start in 0..<length {
    var freq: [Character: Int] = [:]
    var maxFreq = 0
    var majorityChar: Character? = nil
    
    for end in start..<length {
      let char = chars[end]
      freq[char, default: 0] += 1
      if freq[char]! > maxFreq {
        maxFreq = freq[char]!
        majorityChar = char
      }
      
      let substringLength = end - start + 1
      
      if maxFreq > substringLength / 2 {
        dp[end + 1] = min(dp[end + 1], dp[start] + 1)
      }
    }
  }
  
  return dp[length]
}

内容的提问来源于stack exchange，提问作者clearcut3000