Skip to content

395. Longest Substring with At Least K Repeating Characters

Difficulty Topics

Description

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 greater than or equal to k.

 

Example 1:

Input: s = "aaabb", k = 3
Output: 3
Explanation: The longest substring is "aaa", as 'a' is repeated 3 times.

Example 2:

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 <= 104
  • s consists of only lowercase English letters.
  • 1 <= k <= 105

Solution

longest-substring-with-at-least-k-repeating-characters.py
class Solution:
    def longestSubstring(self, st: str, k: int) -> int:

        res = 0
        stack = [st]

        while stack:
            s = stack.pop()
            for c in set(s):
                if s.count(c) < k:
                    stack.extend([ch for ch in s.split(c)])
                    break
            else:    
                res = max(res, len(s))

        return res