BinarySearch 0628 Longest Substring with Character Count of at Least K

Problem statement

https://binarysearch.com/problems/Longest-Substring-with-Character-Count-of-at-Least-K/

Solution

Equal to Leetcode 0395. Longest Substring with At Least K Repeating Characters, but we need to use more efficient algorithm. If we have all frequencies more than k, we can take all string. If not, we can split string into parts and use recursion.

Complexity

It is still O(26n), but it works quite fast.

Code

class Solution:
    def solve(self, s, k):
        for c in set(s):
            if s.count(c) < k:
                return max(self.solve(t, k) for t in s.split(c))
        return len(s)