395. Longest Substring with At Least K Repeating Characters

分治 O(n) time O(1) space
这道题首先要统计字母频，突破口是字母频小于k的字母一定不在任何符合要求的子串里，即把整个字符串分割成若干『有可能符合要求』的子串，这样分而治之，对每个『有可能符合要求』的子串进行分析统计出最长的子串，因为每次分割都会至少去掉一个字母（如果有不符合要求的字母的话），所以最多需要26层，每层总计算步的和是O(n)，这样总的时间复杂度是O(26n)，即O(n)

class Solution {
public:
    int longestSubstring(string s, int k) {
        return dfs(s, 0, size(s), k);
    }

    int dfs(const string &s, int b, int e, int k) {
        if (b == e || k > e - b) return 0; // 如果是空子串或者k过大
        if (k == 0) return e - b; // 如果k为0说明整个子串都是有效的
        int f[26] = {0};
        for (int i = b; i < e; ++i) {
            ++f[s[i] - 'a'];
        }
        int res = 0, p = b; // p表示可能的有效子串的开始下标
        for (int i = b; i <= e; ++i) {
            if (p == b && i == e) return e - b; // 如果整个子串都是有效的
            if (i == e || f[s[i] - 'a'] < k) { // 检查每一个可能的有效子串（包括最后一段，两个condition顺序不能颠倒，否则会越界）
                res = max(res, dfs(s, p, i, k));
                p = i + 1;
            }
        }
        return res;
    }
};

class Solution {
public:
    int longestSubstring(string s, int k) {
        int n = s.length();
        if (n == 0 || k > n) return 0;
        if (k == 0) return n;
        int f[27] = {0};
        for (char c : s) {
            ++f[c - 'a'];
        }
        s += char('z' + 1);
        string str;
        int res = 0;
        bool allValid = true;
        for (int i = 0; i <= n; ++i) {
            if (f[s[i] - 'a'] >= k) {
                str += s[i];
            } else {
                if (i == n && allValid) return n;
                allValid = false;
                res = max(res, longestSubstring(move(str), k));
            }
        }
        return res;
    }
};

class Solution {
public:
    int longestSubstring(string s, int k) {
        int n = s.length();
        if(n == 0 || k > n) return 0;
        if(k == 0) return n;

        int f[26] = {0};
        for(char c : s) {
            ++f[c - 'a'];
        }

        int res = 0;
        for (int i = 0; i < n;) {
            if (f[s[i] - 'a'] < k) {
                ++i;
            } else {
                int j = i + 1;
                for (; j < n && f[s[j] - 'a'] >= k; ++j);
                if (i == 0 && j == n) return j - i;
                res = max(res, longestSubstring(s.substr(i, j - i), k));
                i = j + 1;
            }
        }
        return res;
    }
};

sliding window O(n) time O(1) space
先数一下有多少种不同字符，从1开始枚举不同字符的个数，即相当于window中不同字符的种类数，跑一下类似340. Longest Substring with At Most K Distinct Characters但需要维护一个cntK来保证当前window内所有字符的个数都至少为k个，否则不对res进行更新，最多26种字符，对每一个可能的种类数跑一下sliding window，复杂度为O(26n)

class Solution {
public:
    int longestSubstring(string s, int k) {
        int uniqueChars = countUniqueChars(s), res = 0;
        for (int n = size(s), uniqueChar = 1; uniqueChar <= uniqueChars; ++uniqueChar) {
            int l = 0, cntK = 0;
            unordered_map<char, int> m;
            for (int r = 0; r < n; ++r) {
                if (++m[s[r]] == k) {
                    ++cntK;
                }
                while (size(m) > uniqueChar) {
                    if (m[s[l]] == k) {
                        --cntK;
                    }
                    if (--m[s[l]] == 0) {
                        m.erase(s[l]);
                    }
                    ++l;
                }
                if (cntK == uniqueChar) {
                    res = max(res, r - l + 1);
                }
            }
        }
        return res;
    }

    int countUniqueChars(const string &s) {
        bool visited[26] = {false};
        int res = 0;
        for (char c : s) {
            if (!visited[c - 'a']) {
                visited[c - 'a'] = true;
                ++res;
            }
        }
        return res;
    }
};

分治 worst case O(n²) time
和O(n)的方法相比，这个方法在每一层分割的时候只去掉一个不符合要求的字母，这样，总层数最坏情况有可能是O(n)，因为每一层的计算步是O(n)，所以总的时间复杂度是O(n^2)

class Solution {
public:
    int longestSubstring(string s, int k) {
        int n = s.length();
        if (n == 0 || n < k) return 0;
        int f[26] = {0};
        for (char c : s) {
            ++f[c - 'a'];
        }
        int i = 0;
        for (; i < n && f[s[i] - 'a'] >= k; ++i);
        if (i == n) return n;
        return max(longestSubstring(s.substr(0, i), k), longestSubstring(s.substr(i + 1), k));
    }
};

iterative O(n²) time O(n) space

class Solution {
public:
    int longestSubstring(string s, int k) {
        int res = 0;
        int n = s.length();
        for (int i = 0; i + k <= n;) {
            int mx = i;
            int x = 0;
            int f[26] = {0};
            for (int j = i; j < n; ++j) {
                int c = s[j] - 'a';
                ++f[c];
                if (f[c] < k) {
                    x |= (1 << c);
                } else {
                    x &= ~(1 << c);
                }
                if (x == 0) {
                    res = max(res, j - i + 1);
                    mx = j;
                }
            }
            i = mx + 1;
        }
        return res;
    }
};