https://leetcode.com/problems/longest-substring-with-at-least-k-repeating-characters

First of all, be careful with this problem formulation: 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 less than or equal to k : this is not correct statement, what you actually asked is is more than or equal to k. I spend some time figuring it out.

Now, we will use sliding window approach to find the window of biggest length. However, it is not that easy. Imagine, that we have s = aabbb... and k = 3, what should we do when we reached window aabbb: should we expand it to the right hoping that we will meet another a? Or should we start to move left side of our window? One way to handle this problem is to do several sliding windows passes, where we fix T number of different symbols we must have in our substring. So, we check all posible T = 1, ... 26 (if fact, not 26, but len(Counter(s)) + 1)) and do sliding window pass:

  1. Initialize beg = 0, end = 0, Found = 0: number of elements with frequency more or equal than k, freq is array of frequencies = [0]*26 and MoreEqK = 0, which count number of non-zero frequencies in our freq array.
  2. Now, we check if MoreEqK <=T or not, that is we have T or less different symbols in our window: then we can add element to to right part of our sliding window: we increase its frequency, if this symbol is new, that is frequency become equal to 1, we increment MoreEqK. Also, if frequency become equal to k, we increment Found.
  3. In opposite case it means, that we already have T+1 or more different symbols in or window, so we need to move left side of our sliding window. Again, we check if frequency was equal to k and if it was, we decrease Found by one, if frequency become equal to zero, we decrease MoreEqK.
  4. Finally, if we have exactly T non-zero frequencies and all T of them more or equal than k, we update our result.

Complexity: time complexity is O(26n), because we can potentially have 26 passes over our data. Space complexity is O(26). Yes, I understand, that O(26n) = O(n), but here I want to stress that constant is quite big.

class Solution:
    def longestSubstring(self, s, k):
        result = 0
        for T in range(1, len(Counter(s))+1):
            beg, end, Found, freq, MoreEqK = 0, 0, 0, [0]*26, 0
            while end < len(s):
                if MoreEqK <= T:
                    s_new = ord(s[end]) - 97
                    freq[s_new] += 1
                    if freq[s_new] == 1:
                        MoreEqK += 1
                    if freq[s_new] == k:
                        Found += 1
                    end += 1
                else:
                    symb = ord(s[beg]) - 97
                    beg += 1
                    if freq[symb] == k:
                        Found -= 1
                    freq[symb] -= 1
                    if freq[symb] == 0:
                        MoreEqK -= 1
                            
                if MoreEqK == T and Found == T:
                    result = max(result, end - beg)
                    
        return result

If you like the solution, you can upvote it on leetcode discussion section: Problem 0395