DEV Community

Abhishek Chaudhary
Abhishek Chaudhary

Posted on

Longest Substring with At Least K Repeating Characters

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:

class Solution:
    def lstr(self, s, beg, end, k):
        if end - beg < k:
            return 0
        ctr = [0] * 26
        for i in range(beg, end):
            ctr[ord(s[i]) - ord('a')] += 1
        for i in range(beg, end):
            if ctr[ord(s[i]) - ord('a')] < k:
                return max(self.lstr(s, beg, i, k), self.lstr(s, i + 1, end, k))
        return end - beg


    def longestSubstring(self, s: str, k: int) -> int:
        return self.lstr(s, 0, len(s), k)
Enter fullscreen mode Exit fullscreen mode

Top comments (0)