[LeetCode] 395. Longest Substring with At Least K Repeating Characters #395

grandyang · 2019-05-30T16:20:34Z

Find the length of the longest substring T of a given string (consists of lowercase letters only) such that every character in T appears no less than k times.

Example 1:

Input:
s = "aaabb", k = 3

Output:
3

The longest substring is "aaa", as 'a' is repeated 3 times.

Example 2:

Input:
s = "ababbc", k = 2

Output:
5

The longest substring is "ababb", as 'a' is repeated 2 times and 'b' is repeated 3 times.

这道题给了我们一个字符串s和一个正整数k，让求一个最大子字符串并且每个字符必须至少出现k次。作为 LeetCode 第三次编程比赛的压轴题目，博主再一次没有做出来，虽然难度标识只是 Medium。后来在网上膜拜学习了大神们的解法，发现当时的没做出来的原因主要是卡在了如何快速的判断某一个字符串是否所有的字符都已经满足了至少出现k次这个条件，虽然博主也用 HashMap 建立了字符和其出现次数之间的映射，但是如果每一次都要遍历 HashMap 中的所有字符看其出现次数是否大于等于k，未免有些不高效。而用 mask 就很好的解决了这个问题，由于字母只有 26 个，而整型 mask 有 32 位，足够用了，每一位代表一个字母，如果为1，表示该字母不够k次，如果为0就表示已经出现了k次，这种思路真是太聪明了，隐约记得这种用法在之前的题目中也用过，但是博主并不能举一反三( 沮丧脸:( )，还得继续努力啊。遍历字符串，对于每一个字符，都将其视为起点，然后遍历到末尾，增加 HashMap 中字母的出现次数，如果其小于k，将 mask 的对应位改为1，如果大于等于k，将 mask 对应位改为0。然后看 mask 是否为0，是的话就更新 res 结果，然后把当前满足要求的子字符串的起始位置j保存到 max_idx 中，等内层循环结束后，将外层循环变量i赋值为 max_idx+1，继续循环直至结束，参见代码如下：

解法一：

class Solution {
public:
    int longestSubstring(string s, int k) {
        int res = 0, i = 0, n = s.size();
        while (i + k <= n) {
            int m[26] = {0}, mask = 0, max_idx = i;
            for (int j = i; j < n; ++j) {
                int t = s[j] - 'a';
                ++m[t];
                if (m[t] < k) mask |= (1 << t);
                else mask &= (~(1 << t));
                if (mask == 0) {
                    res = max(res, j - i + 1);
                    max_idx = j;
                }
            }
            i = max_idx + 1;
        }
        return res;
    }
};

虽然上面的方法很机智的使用了 mask 了标记某个子串的字母是否都超过了k，但仍然不是很高效，因为遍历了所有的子串，使得时间复杂度到达了平方级。来想想如何进行优化，因为题目中限定了字符串中只有字母，这意味着最多不同的字母数只有 26 个，最后满足题意的子串中的不同字母数一定是在 [1, 26] 的范围，这样就可以遍历这个范围，每次只找不同字母个数为 cnt，且每个字母至少重复k次的子串，来更新最终结果 res。这里让 cnt 从1遍历到 26，对于每个 cnt，都新建一个大小为 26 的数组 charCnt 来记录每个字母的出现次数，使用的思想其实还是滑动窗口 Sliding Window，使用两个变量 start 和 i 来分别标记窗口的左右边界，当右边界小于n时，进行 while 循环，需要一个变量 valid 来表示当前子串是否满足题意，初始化为 true，还需要一个变量 uniqueCnt 来记录子串中不同字母的个数。此时若 s[i] 这个字母在 charCnt 中的出现次数为0，说明遇到新字母了，uniqueCnt 自增1，同时把该字母的映射值加1。此时由于 uniqueCnt 变大了，有可能会超过之前限定了 cnt，所以这里用一个 while 循环，条件是当 uniqueCnt 大于 cnt ，此时应该收缩滑动窗口的左边界，那么对应的左边界上的字母的映射值要自减1，若减完后为0了，则 uniqueCnt 自减1，注意这里一会后加，一会先减的操作，不要搞晕了。当 uniqueCnt 没超过 cnt 的时候，此时还要看当前窗口中的每个字母的出现次数是否都大于等于k，遇到小于k的字母，则直接 valid 标记为 false 即可。最终若 valid 还是 true，则表示滑动窗口内的字符串是符合题意的，用其长度来更新结果 res 即可，参见代码如下：

解法二：

class Solution {
public:
    int longestSubstring(string s, int k) {
        int res = 0, n = s.size();
        for (int cnt = 1; cnt <= 26; ++cnt) {
            int start = 0, i = 0, uniqueCnt = 0;
            vector<int> charCnt(26);
            while (i < n) {
                bool valid = true;
                if (charCnt[s[i++] - 'a']++ == 0) ++uniqueCnt;
                while (uniqueCnt > cnt) {
                    if (--charCnt[s[start++] - 'a'] == 0) --uniqueCnt;
                }
                for (int j = 0; j < 26; ++j) {
                    if (charCnt[j] > 0 && charCnt[j] < k) valid = false;
                }
                if (valid) res = max(res, i - start);
            }
        }    
        return res;
    }
};

下面这种解法用的分治法 Divide and Conquer 的思想，看起来简洁了不少，但是个人感觉比较难想，这里使用了一个变量 max_idx，是用来分割子串的，实现开始统计好了字符串s的每个字母出现的次数，然后再次遍历每个字母，若当前字母的出现次数小于k了，则从开头到前一个字母的范围内的子串可能是满足题意的，还需要对前面的子串进一步调用递归，用返回值来更新当前结果 res，此时变量 ok 标记为 false，表示当前整个字符串s是不符合题意的，因为有字母出现次数小于k，此时 max_idx 更新为 i+1，表示再从新的位置开始找下一个出现次数小于k的字母的位置，可以对新的范围的子串继续调用递归。当 for 循环结束后，若 ok 是 true，说明整个s串都是符合题意的，直接返回n，否则要对 [max_idx, n-1] 范围内的子串再次调用递归，因为这个区间的子串也可能是符合题意的，还是用返回值跟结果 res 比较，谁大就返回谁，参见代码如下：

解法三：

class Solution {
public:
    int longestSubstring(string s, int k) {
        int n = s.size(), max_idx = 0, res = 0;
        int m[128] = {0};
        bool ok = true;
        for (char c : s) ++m[c];
        for (int i = 0; i < n; ++i) {
            if (m[s[i]] < k) {
                res = max(res, longestSubstring(s.substr(max_idx, i - max_idx), k));
                ok = false;
                max_idx = i + 1;
            }
        }
        return ok ? n : max(res, longestSubstring(s.substr(max_idx, n - max_idx), k));
    }
};

Github 同步地址：

#395

类似题目：

Longest Substring with At Most K Distinct Characters

Longest Substring with At Most Two Distinct Characters

Longest Substring Without Repeating Characters

参考资料：

https://leetcode.com/problems/longest-substring-with-at-least-k-repeating-characters/

https://leetcode.com/problems/longest-substring-with-at-least-k-repeating-characters/discuss/87834/onlogn-recursive-cpp-solution

https://leetcode.com/problems/longest-substring-with-at-least-k-repeating-characters/discuss/87739/Java-Strict-O(N)-Two-Pointer-Solution

https://leetcode.com/problems/longest-substring-with-at-least-k-repeating-characters/discuss/87749/Two-short-C%2B%2B-solutions-(3ms-and-6ms)

LeetCode All in One 题目讲解汇总(持续更新中...)