卖萌的弱渣

I am stupid, I am hungry.

Longest Substring With at Least K Repeating Characters

Find the length of the longest substring T of a given string (consists of lowercase letters only) such that every character in T appears no less than k times.

Example 1:

1
2
3
4
5
6
7

Input:
s = "aaabb", k = 3

Output:
3

The longest substring is "aaa", as 'a' is repeated 3 times.

Example 2:

1
2
3
4
5
6
7

Input:
s = "ababbc", k = 2

Output:
5

The longest substring is "ababb", as 'a' is repeated 2 times and 'b' is repeated 3 times.

Solution

  • 以出现次数不到k的字符做split. 递归调用，返回最大值
(Longest-Substring-with-at-least-k-repeating-character.py) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution(object):
    def longestSubstring(self, s, k):
        """
        :type s: str
        :type k: int
        :rtype: int
        """

        for x in set(s):
            # x没有重复k次
            if s.count(x) < k:
                return max(self.longestSubstring(t,k) for t in s.split(x))
        # 所有s中字符都符合
        return len(s)