先整體考慮，如果某個(gè)字符在整個(gè)字符串中的出現(xiàn)次數(shù) < k，那它一定不會(huì)出現(xiàn)在合法子串中。
s: aaabbaa,k: 3，b 只出現(xiàn) 2 次，它肯定不會(huì)出現(xiàn)在合法子串中，要到它的兩側(cè)找。
考察aaa和aa，變成一個(gè)規(guī)模較小的子問題，遞歸去求aaa和aa中合法子串的最長長度。
當(dāng)遞歸到子問題的規(guī)模足夠小，即，子串的長度小于 k，即便子串的字符都相同，字符的出現(xiàn)次數(shù)也小于 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：為字符串的長度

Σ 為字符集

時(shí)間復(fù)雜度：O（N⋅∣Σ∣）

空間復(fù)雜度：O（∣Σ∣^2）

方法二：滑動(dòng)窗口（go）

對于給定的字符種類數(shù)量 t，我們維護(hù)滑動(dòng)窗口的左右邊界 l,r 滑動(dòng)窗口內(nèi)部每個(gè)字符出現(xiàn)的次數(shù) cnt，以及滑動(dòng)窗口內(nèi)的字符種類數(shù)目 total。

當(dāng) total>t 時(shí)，我們不斷地右移左邊界 l，并對應(yīng)地更新 cnt 以及 total，直到 total≤t 為止。這樣，對于任何一個(gè)右邊界 r，我們都能找到最小的 l（記為 l_{min}），使得 s[l_{min}...r]之間的字符種類數(shù)目不多于 t。

通過維護(hù)額外的計(jì)數(shù)器 less，我們無需遍歷 cnt 數(shù)組，就能知道每個(gè)字符是否都出現(xiàn)了至少 k 次，同時(shí)可以在每次循環(huán)時(shí)，在常數(shù)時(shí)間內(nèi)更新計(jì)數(shù)器的取值。

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：為字符串的長度

Σ 為字符集

時(shí)間復(fù)雜度：O（N⋅∣Σ∣+∣Σ∣^2)

空間復(fù)雜度：O(∣Σ∣)

以上就是Go Java算法之K個(gè)重復(fù)字符最長子串詳解的詳細(xì)內(nèi)容，更多關(guān)于Go Java算法重復(fù)字符子串的資料請關(guān)注腳本之家其它相關(guān)文章！

您可能感興趣的文章: