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

Given a string s and an integer k, return the length of the longest substring of s such that the frequency of each character in this substring is greater than or equal to k.

if no such substring exists, return 0.

Example 1:
Input: s = “aaabb”, k = 3
Output: 3
Explanation: The longest substring is “aaa”, as ‘a’ is repeated 3 times.

Example 2:
Input: s = “ababbc”, k = 2
Output: 5
Explanation: The longest substring is “ababb”, as ‘a’ is repeated 2 times and ‘b’ is repeated 3 times.

Constraints:
1 <= s.length <= 104
s consists of only lowercase English letters.
1 <= k <= 105

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

给你一个字符串 s 和一个整数 k ，请你找出 s 中的最长子串， 要求该子串中的每一字符出现次数都不少于 k 。返回这一子串的长度。

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

思路一 - 递归

首先暴力解就是以一个 O(n^2) 的复杂度去遍历input字符串，看看字符串中是否存在一个 [s.charAt(j), s.charAt(i)] 的子串满足题意。这个做法会超时。

递归/分治的思路是首先统计一下 input 字符串里每个不同字母的出现次数。然后我们再次遍历 input 字符串，当走到某个位置 i 的时候，看一下这个位置指向的字母的出现次数是否大于等于 k，如果不满足这个条件，则说明这个字母不能成为题目要求的子串的一部分，就要从这个地方把字符串分割成两半再往下递归看。

复杂度

时间O(n^2)
空间O(n)

代码

Java实现

class Solution {
	public int longestSubstring(String s, int k) {
		return helper(s, k, 0, s.length());
	}

	private int helper(String s, int k, int start, int end) {
		// 整个字符串的长度都不足k，直接返回0
		if (end - start < k) {
			return 0;
		}
		// 统计每个字符出现的次数
		int[] count = new int[26];
		for (int i = start; i < end; i++) {
			count[s.charAt(i) - 'a']++;
		}

		// 找到第一个不满足条件的字符的位置
		for (int i = start; i < end; i++) {
			if (count[s.charAt(i) - 'a'] < k && count[s.charAt(i) - 'a'] > 0) {
				int nextStart = i + 1;
				while (nextStart < end && count[s.charAt(nextStart) - 'a'] < k) {
					nextStart++;
				}
				return Math.max(helper(s, k, 0, i), helper(s, k, nextStart, end));
			}
		}
		return end - start;
	}
}
// time complexity: O(n^2), space complexity: O(n)

思路二 - 滑动窗口

这里我们把题目要求拆分一下。既然题目说了只有小写字母（这里好像是不太对，因为用数组统计的时候如果数组长度只创建成26是会越界的），那么我们可以从 1 到 26 去试探。这里我们试探的是找一个子串，其中包含了一个，两个，三个或者。。26 个不同字符，每个字符出现次数不少于 K。这样一来我们就可以把题目转化成类似 159 和 340 那样的做法了。

复杂度

时间O(n)
空间O(n)

代码

Java实现

class Solution {
    public int longestSubstring(String s, int k) {
        int res = 0;
        // 试探input字符串中是否能找到一个最长的字符串，存在有numUniqueTarget个不同字符
        // 我们这里是从1 - 26一个个去试探
        for (int numUniqueTarget = 1; numUniqueTarget <= 26; numUniqueTarget++) {
            res = Math.max(res, helper(s, k, numUniqueTarget));
        }
        return res;
    }

    // sliding window模板
    private int helper(String s, int k, int i) {
        int[] map = new int[256];
        int start = 0;
        int end = 0;
        int res = Integer.MIN_VALUE;
        // 子串内unique的字母个数
        int counter = 0;
        // 出现次数不少于K的字母个数
        int numNoLessThanK = 0;
        while (end < s.length()) {
            char c1 = s.charAt(end);
            if (map[c1]++ == 0) {
                counter++;
            }
            if (map[c1] == k) {
                numNoLessThanK++;
            }
            end++;

            while (counter > i) {
                char c2 = s.charAt(start);
                if (map[c2]-- == k) {
                    numNoLessThanK--;
                }
                if (map[c2] == 0) {
                    counter--;
                }
                start++;
            }

            if (counter == numNoLessThanK) {
                res = Math.max(res, end - start);
            }
        }
        return res;
    }
}