想要精通算法和SQL的成长之路 - 至少有 K 个重复字符的最长子串

前言

想要精通算法和SQL的成长之路 - 系列导航

一. 至少有 K 个重复字符的最长子串

原题链接

看到这类 区间求长 性质的题目，我们可能第一反应都是用滑动窗口来完成。但是滑动窗口需要考虑的重要点是什么？

• 什么条件下滑动窗口的右边界可以移动（扩）
• 什么条件下滑动窗口的左边界可以移动（缩）

1.1 滑动窗口的前提：二段性

对于本题而言：我们假设滑动窗口区间长度是 n，并尝试假设这个区间内的字符一定满足题目的要求。那么当滑动窗口向右移动的时候，在第 n+1 位置的字符加入到窗口后，是否同样一定满足题目要求？

• 如果新位置的字符在原有的区间内出现过，那么窗口区间内的字符已经满足出现次数 > k 了，此时必然依旧满足。
• 如果新位置的字符在原有的区间内没出现过，在新字符的加入后，新窗口内的元素必然不满足：所有字符的出现次数 > k。

我们在使用滑动窗口过程中，如果得到一个最优解，我们知道：

1. 最优解左边界左侧的字符一定不会出现在最优解子串中。
2. 最优解右边界右侧的字符也一定不会出现在最优解子串中。
3. 如果出现，那么最优解就不再是最优解。

看似是个废话，其实想表达的就是：最优解左右边界两端的字符，倘若把他们加入到最优解中，一定是不满足条件的。 而最优解部分一定是满足条件的。

这就是滑动窗口的一个使用前提：二段性。而经过上面的分析，可见该题目在常规做法下不具备二段性。 因此需要我们手动增加一个限制。

1.2 手动增加限制，让其具备二段性

我们注意到，题目的字符种类有26种，那么我们可以从这个切入点出发：

• 我们假设局部最优解的字符种类数有charCountLimit个。
• 那么在遍历字符串的同时，我们需要维护当前窗口内的字符种类数 < charCountLimit个。在这个前提下，我们可以不断地扩充窗口（右指针移动）。
• 当字符种类数量 > charCountLimit 的限制时，我们就可以将窗口缩小（左指针移动）。
• 遍历过程中，我们维护每个字符出现的次数，以及当前窗口内的两个属性：
• totalChar：当前窗口内不同的字符类型数量。
• sumChar：窗口内满足出现次数 >=k 的字符类型数量。
• 最终只要totalChar == sumChar，说明满足条件，该窗口内的所有字符，都满足出现次数 > k，可以更新最大子串长度。

1.3 完整代码（滑动窗口）

代码如下：

public int longestSubstring(String s, int k) {
    char[] cs = s.toCharArray();
    int res = 0, len = cs.length;
    int[] csCount = new int[26];
    // 当前字符串元素数量：curCharCount
    for (int charCountLimit = 1; charCountLimit <= 26; charCountLimit++) {
        // 重置各个元素出现的次数
        Arrays.fill(csCount, 0);
        // totalChar:当前窗口内不同的字符类型数量。sumChar:窗口内满足出现次数 >=k 的字符类型数量
        int left = 0, right = 0, totalChar = 0, sumChar = 0;
        // 统计每个元素出现的次数,charIndex:字符对应的下标
        while (right < len) {
            // 右边界对应的字符（用数组形式表示）
            int rightCharIndex = cs[right] - 'a';
            csCount[rightCharIndex]++;
            // 第一次出现，则增加区间内的字符总数
            if (csCount[rightCharIndex] == 1) {
                totalChar++;
            }
            // 第一次满足条件（后续有相同字符的话一定满足），则统计下满足条件的字符数量
            if (csCount[rightCharIndex] == k) {
                sumChar++;
            }
            // 如果当前总字符种类数量 > 我们限制的数量，我们移动左窗口，希望减少总字符种类数量
            while (totalChar > charCountLimit) {
                // 左边界对应的字符（用数组形式表示）
                int leftCharIndex = cs[left] - 'a';
                if (csCount[leftCharIndex] == 1) {
                    totalChar--;
                }
                if (csCount[leftCharIndex] == k) {
                    sumChar--;
                }
                csCount[leftCharIndex]--;
                // 左窗口移动
                left++;
            }
            if (totalChar == sumChar) {
                res = Math.max(res, right - left + 1);
            }
            // 右窗口移动
            right++;
        }
    }
    return res;
}
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

1.4 另一种解题思路（递归）

1. 我们直接统计整个字符串中，每个字符的出现次数。
2. 题目要求是：最优解的每个字符串都出现了至少 k 次。那么我们反过来，我们只要把不满足k次的字符给挑出来删除，剩下的是不是就是满足条件的了？那么题目所求最长子串长度，就是删除后的字符总长。
3. 我们假设某个字符 c ，他不满足题目要求，我们把字符串根据c来进行分割。对于每个子串（分割后必定不包含字符c），我们再求对应的最长子串长度即可。

public int longestSubstring(String s, int k) {
    if (s.length() < k) {
        return 0;
    }
    HashMap<Character, Integer> count = new HashMap();
    for (int i = 0; i < s.length(); i++) {
        count.put(s.charAt(i), count.getOrDefault(s.charAt(i), 0) + 1);
    }
    for (char c : count.keySet()) {
        // 找到不满足的字符串c
        if (count.get(c) < k) {
            int res = 0;
            // 根据c进行分割，分割后的各个子串不包含c
            for (String t : s.split(String.valueOf(c))) {
                // 求得最大子串长度
                res = Math.max(res, longestSubstring(t, k));
            }
            return res;
        }
    }
    // 如果到这一步了，这里的字符串必定满足题目要求，因为我们已经把不符合调剂的字符都删除了
    return s.length();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23