Longest Substring with At Least K Repeating Characters

Problem Id: 395 Difficulty: Medium


Intuition

Solution


class Solution:
    def longestSubstring(self, s: str, k: int) -> int:
        if k <= 1:
            return len(s)
        if not s:
            return 0

        less = []
        for c in string.ascii_lowercase:
            count_c = s.count(c)
            if count_c and count_c < k:
                less.append(c)

        if not less:
            return len(s)

        ans = 0
        start = 0
        end = 0
        for i in range(len(s)):
            c = s[i]
            if c in less:
                ans = max(ans, self.longestSubstring(s[start:end], k))
                start = end = i + 1
            else:
                end = i + 1
        if start != end:
            ans = max(ans, self.longestSubstring(s[start:end], k))
        return ans