Go Java算法之K个重复字符最长子串详解

至少有K个重复字符的最长子串

给你一个字符串 s 和一个整数 k ，请你找出 s 中的最长子串， 要求该子串中的每一字符出现次数都不少于 k 。返回这一子串的长度。

• 示例 1：

输入：s = "aaabb", k = 3

输出：3

解释：最长子串为 "aaa" ，其中 'a' 重复了 3 次。

• 示例 2：

输入：s = "ababbc", k = 2

输出：5

解释：最长子串为 "ababb" ，其中 'a' 重复了 2 次， 'b' 重复了 3 次。

方法一：分治（Java）

对于字符串 s，如果存在某个字符 ch，它的出现次数大于 0 且小于 k，则任何包含 ch 的子串都不可能满足要求。

也就是说，我们将字符串按照 ch 切分成若干段，则满足要求的最长子串一定出现在某个被切分的段内，而不能跨越一个或多个段。

具体思路：

• 先整体考虑，如果某个字符在整个字符串中的出现次数 < k，那它一定不会出现在合法子串中。

• s: aaabbaa,k: 3，b 只出现 2 次，它肯定不会出现在合法子串中，要到它的两侧找。

• 考察aaa和aa，变成一个规模较小的子问题，递归去求aaa和aa中合法子串的最长长度。

• 当递归到子问题的规模足够小，即，子串的长度小于 k，即便子串的字符都相同，字符的出现次数也小于 k，所以没有合法子串，返回 0

class Solution {
  public int longestSubstring(String s, int k) {
      int n = s.length();
      return dfs(s, 0, n - 1, k);
  }
  public int dfs(String s, int l, int r, int k) {
      int[] cnt = new int[26];
      for (int i = l; i <= r; i++) {
          cnt[s.charAt(i) - 'a']++;
      }
      char split = 0;
      for (int i = 0; i < 26; i++) {
          if (cnt[i] > 0 && cnt[i] < k) {
              split = (char) (i + 'a');
              break;
          }
      }
      if (split == 0) {
          return r - l + 1;
      }
      int i = l;
      int ret = 0;
      while (i <= r) {
          while (i <= r && s.charAt(i) == split) {
              i++;
          }
          if (i > r) {
              break;
          }
          int start = i;
          while (i <= r && s.charAt(i) != split) {
              i++;
          }
          int length = dfs(s, start, i - 1, k);
          ret = Math.max(ret, length);
      }
      return ret;
  }
}

N：为字符串的长度

&Sigma; 为字符集

时间复杂度：O（N&sdot;∣&Sigma;∣）

空间复杂度：O（∣&Sigma;∣^2）

方法二：滑动窗口（go）

对于给定的字符种类数量 t，我们维护滑动窗口的左右边界 l,r 滑动窗口内部每个字符出现的次数 cnt，以及滑动窗口内的字符种类数目 total。

当 total>t 时，我们不断地右移左边界 l，并对应地更新 cnt 以及 total，直到 total&le;t 为止。这样，对于任何一个右边界 r，我们都能找到最小的 l（记为 l_{min}），使得 s[l_{min}...r]之间的字符种类数目不多于 t。

通过维护额外的计数器 less，我们无需遍历 cnt 数组，就能知道每个字符是否都出现了至少 k 次，同时可以在每次循环时，在常数时间内更新计数器的取值。

func longestSubstring(s string, k int) (ans int) {
  for t := 1; t <= 26; t++ {
      cnt := [26]int{}
      total := 0
      lessK := 0
      l := 0
      for r, ch := range s {
          ch -= 'a'
          if cnt[ch] == 0 {
              total++
              lessK++
          }
          cnt[ch]++
          if cnt[ch] == k {
              lessK--
          }
          for total > t {
              ch := s[l] - 'a'
              if cnt[ch] == k {
                  lessK++
              }
              cnt[ch]--
              if cnt[ch] == 0 {
                  total--
                  lessK--
              }
              l++
          }
          if lessK == 0 {
              ans = max(ans, r-l+1)
          }
      }
  }
  return ans
}
func max(a, b int) int {
  if a > b {
      return a
  }
  return b
}

N：为字符串的长度

&Sigma; 为字符集

时间复杂度：O（N&sdot;∣&Sigma;∣+∣&Sigma;∣^2)

空间复杂度：O(∣&Sigma;∣)

来源：https://juejin.cn/post/7136203034983399432