395. Longest Substring with At Least K Repeating Characters

一開始以為是dp, 想了好久找不到規則, 後來看解答才知道有一種聰明的divide and conquer

我們先算所有字母出現的次數

接著從頭開始找, mid = 0, 如果當前的字母是大於k次的, 我們就往下找, 直到字母出現小於k次

倘若mid的值就是string的長度, 如果mid 為整個字串的長度, 代表整個string都合格, 直接回傳

我們把substr從頭到這個mid, 再遞回下去找, 為什麼呢, 因為很有可能, 這個子字串的並不是真正合格的字串

這樣說有點模糊, 我們給個例子

abaacbb

按照我們上面找的, k = 3的話, mid會落在c就中斷, 可是

abaa k = 3

並不是我們要的值, 因為b在這個裡面只出現一次, 所以我們得再做一次檢查

最後我們在跳過跟本不合格的字, 最後在另外一邊來查找

在回傳兩邊的最大值, 就結束了

這個應該沒做過也很難想到, 尤其是在看過一堆最長子字串的題目等等

class Solution {
public:
    int longestSubstring(string s, int k) {
        int n = s.size();
        vector<int> table(26,0);
        for(char c: s){
            table[c - 'a']++;
        }
        int mid = 0;
        while(mid < n && table[s[mid] - 'a'] >=k){
            mid++;
        }
        if(mid == n) return n;
        int left = longestSubstring(s.substr(0, mid), k);
        while(mid < n && table[s[mid] - 'a'] < k){
            mid++;
        }
        int right = longestSubstring(s.substr(mid), k);
        return max(left, right);
    }
};