Longest Substring with At Least K Repeating Characters LeetCode solution in Python

1
# Runtime: 57 ms (Top 73.85%) | Memory: 14.4 MB (Top 21.39%)
2
from collections import Counter
3

4

5
class Solution:
6
    def longestSubstring(self, s: str, k: int) -> int:
7
        return get_longest_substring(s, k)
8

9

10
def get_longest_substring(s, k):
11
    if len(s) == 0:
12
        return 0
13
    c = Counter(s)
14
    low_freq_char = set([char for char, freq in c.items() if freq < k])
15
    # base case
16
    if len(low_freq_char) == 0:
17
        return len(s)
18
    # recursively split str into substr
19
    division_points = [i for i in range(len(s)) if s[i] in low_freq_char]
20
    substr_lst = []
21
    # start
22
    substr_lst.append(s[: division_points[0]])
23
    # middle
24
    for i in range(len(division_points) - 1):
25
        substr_lst.append(s[division_points[i] + 1 : division_points[i + 1]])
26
    # end
27
    substr_lst.append(s[division_points[-1] + 1 :])
28
    return max([get_longest_substring(substr, k) for substr in substr_lst])