LeetCode: 395. Longest Substring with At Least K Repeating Characters

Idea: Any characters that have frequencies less than k work as a breakpoints, meaning that the substring we're looking for can't include that particular character. So, recursively look for substrings while excluding those characters. Time complexity is O(N).

from collections import Counter
class Solution:
    def longestSubstring(self, s: str, k: int) -> int:
        return self.helper(s, k)
        
    def helper(self, s, k):
        if not s:
            return 0
        c = Counter(s)
        bp = set()
        for key, val in c.items():
            if val < k:
                bp.add(key)
        if not bp:
            return len(s)
        ret = 0
        i = 0
        for j in range(len(s)):
            if s[j] in bp:
                ret = max(ret, self.helper(s[i:j], k))
                i = j + 1
        ret = max(ret, self.helper(s[i:], k))
        return ret

 

Same idea, but more pythonic code would be as below.

class Solution:
    def longestSubstring(self, s: str, k: int) -> int:
        return self.helper(s, k)
        
    def helper(self, s, k):
        if not s or len(s) < k:
            return 0
        c = min(set(s), key=s.count)
        if s.count(c) >= k:
            return len(s)
        return max(self.longestSubstring(t, k) for t in s.split(c))