题目

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

示例 1:

1
2
3
4
5
6
7


输入:
s = "aaabb", k = 3

输出:
3

最长子串为 "aaa" ，其中 'a' 重复了 3 次。

示例 2:

1
2
3
4
5
6
7


输入:
s = "ababbc", k = 2

输出:
5

最长子串为 "ababb" ，其中 'a' 重复了 2 次， 'b' 重复了 3 次。

题解

这道题没有做出来，看了题解后，感觉这道题并不是动态规划。

参考讨论，这道题的实现如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29


int count(const char* chars, int k, int p1, int p2){
    if (p2 - p1 + 1 < k)return 0;
    vector<int> v(26);
    for (int i = p1;i <= p2;i++)
        v[chars[i] - 'a']++;

    while (p2 - p1 + 1 >= k && v[chars[p1] - 'a'] < k)
        p1++;
    while (p2 - p1 + 1 >= k &&v[chars[p2] - 'a'] < k)
        p2--;

    if (p2 - p1 + 1 < k)return 0;

    for (int i = p1;i <= p2;i++) {
        if (v[chars[i] - 'a'] < k) {
            return max(count(chars, k, p1, i - 1), count(chars, k, i + 1, p2));
        }
    }

    return p2 - p1 + 1;
}

int longestSubstring(string s, int k) {
    int len = s.size();
    if (len == 0 || len < k) return 0;
    if (k < 2) return len;

    return count(s.c_str(), k, 0, len - 1);
}

其大致思想是，首先统计所有字母的顺序，之后从两边往内遍历判断，从两边过滤掉那些次数少于k的字母。之后遍历剩下的这些字母，如果哪个字母数量少于k，那就从这里分割，将其分割成两个字串，之后分别再分别对这两个字串递归求解。

下面以官方给的ababbc为例看下相关的过程。

首先统计ababbc字串中各个字母出现的次数，a出现了2次，b出现了3次，而c出现了1次。我们从两边往中间判断过滤。首先是左边，a出现2次，没问题。接下来再看右边，c出现1次，过滤掉，b出现3次，满足需求。

接下来对ababb字串进行遍历，判断其中的字母是否有小于2的情况，发现没有，那么返回该字串的长度。

总的来说，感觉这道题并不是动态规划，虽然有子问题，但其并不存在状态转移方程。最后，还是需要好好领会下这类题目的解题思路，在后面碰到其他题目时，能够举一反三。

另外，后面看了网上其他的思考，都有提到滑动窗口，滑动窗口的算法自己参考了网上的一些说明，但自己想了好久均为想出来，遂只能参考网上的解答，网上的实现如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30


int longestSubstring(string s, int k) {//sliding window
    int longstr=0;
    // 循环1到26种不同字符种类
    for(int needalpha=1;needalpha<=26;needalpha++){
        unordered_map<char,int> map;
        int left=0,right=0;
        int windowalpha=0; // 窗口范围内的不同字符数量
        int nolessthank=0; // 记录满足k个数量的字符数
        while(right<s.size()){
            // 如果map中数量为0，那么窗口不同字符数量+1
            if(map[s[right]]++==0) windowalpha++;
            // 如果map中数量为k，那么满足k个数量的字符数+1
            if(map[s[right]]==k) nolessthank++;
            right++;
            
            // 如果窗口中的不同字符数>循环中指定的字符数，那么移动左指针
            while(windowalpha>needalpha){
                if(map[s[left]]--==k) nolessthank--;
                if(map[s[left]]==0) windowalpha--;
                left++;
            }
            // 如果窗口中不同字符数量与循环指定的数量相同，且
            // k个数量的字符与窗口中的字符数量相同，那么更新长度
            if(windowalpha==needalpha&&nolessthank==windowalpha){
                longstr=max(longstr,right-left);
            }    
        }
    }
    return longstr;
}

对其的解释已经放在注释中了。这里与常规的滑动窗口不一样的是在最外面有一层循环，这层循环用来指定满足需求的字符串中共有几个不同的字符。之所以这样，是因为无法判断左指针移动的条件。

我自己在思考时，也确实是被左指针移动的判断条件给难住了。而上面的实现中，是以窗口中的不同字符数量作为判断条件，通过指定不同的数量，进而得到不同数量下的最大长度，而这些长度中的最大长度便是我们要求的长度。

当然上面的这个程序还有些优化的空间，它默认循环26次，其实可以提前判断下字符串中共有多少个不同字符的数量，之后再根据这个数量进行循环。

滑动窗口主要参考下面两篇文章：