【leetcode】395. 至少有K个重复字符的最长子串

题目

找到给定字符串（由小写字符组成）中的最长子串 T ， 要求 T 中的每一字符出现次数都不少于 k 。输出 T 的长度。

示例 1:

输入:
s = “aaabb”, k = 3

输出:
3

最长子串为 “aaa” ，其中 ‘a’ 重复了 3 次。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-substring-with-at-least-k-repeating-characters
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

这个题目一开始我是用的滑动窗口的思路。
首先统计一下字符串中每个字符的个数，当滑动窗口的滑到一个字符的个数小于k的时候就缩小窗口，统计一下窗口内部满足条件的子串的长度。然后就有一些小小的问题，比如说str = “abbbaca”, k = 3。
当滑动窗口第一次停下来，进行内部元素统计的时候是 abbba , 这个时候，怎么缩小滑动窗口就有些困难。因为需要将l, r 同时进行一个调整。
我感觉滑动窗口的解决思路是首先获得一个[l, r]最大最小的可行解空间，然后增大l, 求一个最优解。但是，滑动到第二个a的时候，我无法得知abbb是一个最小的可行解，只有滑动到c的时候，我才知道abbbac是一个可行解，但不是最小的可行解，就造成了需要同时调整l, r。
所以就可以采用一个分治的思想，将原问题划分问一些子问题和另一些子问题，然后分别进行处理，因为无法很好的分成一个子问题和另一些子问题。
所以采用了递归分治的做法

代码

class Solution {
   
public:
    int longestSubstring(string s, int k) {
   
        if (k <= 1) return s.size();
        if (s.empty() || s.size() < k) return 0;
        
        vector<int> hash(128, 0);
        for (char c : s) ++hash[c];
        
        int i = 0;
        while (i < s.size() && hash[s[i]] >= k) ++i;
        if (i == s.size()) return s.size();

        int l = longestSubstring(s.substr(0, i), k);
        while (i < s.size() && hash[s[i]] < k) ++i;
        int r = longestSubstring(s.substr(i), k);
        
        return max(l, r);
    }
};

总结

滑动窗口应该是分治法的一个特例，
滑动窗口是将问题分成了一个子问题和另一些子问题
窗口内部就是一个子问题，然后在这个子问题内部求一个最优解

而这个题目，不太容易将问题划分为一个子问题和另一些子问题，
但是划分为一些子问题和另一些子问题比较容易，
所以就用一个递归的方法来解决。