KK's blog

每天积累多一些

0%

LeetCode 395 Longest Substring with At Least K Repeating Characters

Posted on Edited on Disqus:

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字母存储法解决。
前面的sliding window题都要求字符种数是固定的，否则不单调，例如本题。如aabbcc, i=1, “aa”,满足题目条件，但向右移就不满足条件，但事实再移一位就满足条件
若修改为n=2, 也就是收缩条件为字符窗口必须有两种字符，若出现3个就shrink直到只有两个字符，而这个窗口忽略了每个字符都要出现k个的条件。
举例aabb, i=3, res=4. i=4, aabbc, 出现3种字符，shrink到bbc, 再扩展到bbcc.

此题关键在于将收缩条件：每个字符出现k次转化成字符种数=n再计算k

解题步骤：

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代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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)

Free mock interview