forked from YuriSpiridonov/LeetCode
-
Notifications
You must be signed in to change notification settings - Fork 0
/
395.LongestSubstringwithAtLeastKRepeatingCharacters.py
44 lines (38 loc) · 1.42 KB
/
395.LongestSubstringwithAtLeastKRepeatingCharacters.py
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
"""
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 less than or equal to k.
Example:
Input: s = "aaabb", k = 3
Output: 3
Explanation: The longest substring is "aaa", as 'a' is repeated 3 times.
Example:
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^4
- s consists of only lowercase English letters.
- 1 <= k <= 10^5
"""
#Difficulty: Medium
#31 / 31 test cases passed.
#Runtime: 24 ms
#Memory Usage: 14.5 MB
#Runtime: 24 ms, faster than 98.68% of Python3 online submissions for Longest Substring with At Least K Repeating Characters.
#Memory Usage: 14.5 MB, less than 16.41% of Python3 online submissions for Longest Substring with At Least K Repeating Characters.
import collections
class Solution:
def longestSubstring(self, s: str, k: int) -> int:
if k > len(s):
return 0
chars = collections.Counter(s)
for char, count in chars.items():
if count < k:
length = 0
subs = s.split(char)
for sub in subs:
length = max(length, self.longestSubstring(sub, k))
return length
return len(s)