Go Java算法之K個重復(fù)字符最長子串詳解

更新時間：2022年08月31日 16:21:08 作者：黃丫丫

這篇文章主要為大家介紹了Go Java算法之K個重復(fù)字符最長子串詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪

至少有K個重復(fù)字符的最長子串

給你一個字符串 s 和一個整數(shù) k ，請你找出 s 中的最長子串，要求該子串中的每一字符出現(xiàn)次數(shù)都不少于 k 。返回這一子串的長度。

示例 1：

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

輸出：3

解釋：最長子串為 "aaa" ，其中 'a' 重復(fù)了 3 次。

示例 2：

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

輸出：5

解釋：最長子串為 "ababb" ，其中 'a' 重復(fù)了 2 次， 'b' 重復(fù)了 3 次。

方法一：分治（Java）

對于字符串 s，如果存在某個字符 ch，它的出現(xiàn)次數(shù)大于 0 且小于 k，則任何包含 ch 的子串都不可能滿足要求。

也就是說，我們將字符串按照 ch 切分成若干段，則滿足要求的最長子串一定出現(xiàn)在某個被切分的段內(nèi)，而不能跨越一個或多個段。

具體思路：

先整體考慮，如果某個字符在整個字符串中的出現(xiàn)次數(shù) < k，那它一定不會出現(xiàn)在合法子串中。
s: aaabbaa,k: 3，b 只出現(xiàn) 2 次，它肯定不會出現(xiàn)在合法子串中，要到它的兩側(cè)找。
考察aaa和aa，變成一個規(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：為字符串的長度

Σ 為字符集

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

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

方法二：滑動窗口（go）

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

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

通過維護(hù)額外的計數(shù)器 less，我們無需遍歷 cnt 數(shù)組，就能知道每個字符是否都出現(xiàn)了至少 k 次，同時可以在每次循環(huán)時，在常數(shù)時間內(nèi)更新計數(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：為字符串的長度

Σ 為字符集

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

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

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

您可能感興趣的文章: