LeetCode 395 Longest Substring with At Least K Repeating Characters

LeetCode

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.

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 <= 10<sup>4</sup> s consists of only lowercase English letters.
* 1 <= k <= 10<sup>5</sup>

题目大意：

求最长每种字符至少k个的子串

解题思路：

类似于L003 Longest Substring Without Repeating Characters用双指针法，难点是每种字符，用26字母存储法解决。

解题步骤：

N/A

注意事项：

1. 按多少种不同字符来做sliding window。有1-26种。
2. 子函数求给定种数下的最长子串，所以满足条件在外循环不在内循环，还需进一步统计每种字符是否符合k个。内循环为不满足条件的情况len(char_to_count) == n + 1
3. char_to_count记录每种字符个数, valid_count是子串[left, i]之间满足题意中个数大于等于k的种数。

Python代码：

def longestSubstring(self, s: str, k: int) -> int:
	res = 0
	for i in range(1, 27):
		res = max(res, self.longest_substring(s, k, i))
	return res

def longest_substring(self, s, k, n) -> int:
	left, char_to_count = 0, collections.defaultdict(int)
	res = 0
	for i in range(len(s)):
		char_to_count[ord(s[i]) - ord('a')] += 1
		while len(char_to_count) == n + 1:
			char_to_count[ord(s[left]) - ord('a')] -= 1 # use left not i
			if char_to_count[ord(s[left]) - ord('a')] == 0:
				char_to_count.pop(ord(s[left]) - ord('a'))
			left += 1
		valid_count = len([_ for _ in char_to_count.values() if _ >= k])
		if len(char_to_count) == valid_count:
			res = max(res, i - left + 1)
	return res

算法分析：

时间复杂度为O(26*26n)，空间复杂度O(n)