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.

&nbsp;
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.


&nbsp;
Constraints:


	1 &lt;= s.length &lt;= 104
	s consists of only lowercase English letters.
	1 &lt;= k &lt;= 105


from collections import Counter

class Solution:
    def longestSubstring(self, s: str, k: int) -> int:
        return get_longest_substring(s, k)

def get_longest_substring(s, k):
    if len(s) == 0: return 0
    c = Counter(s)
    low_freq_char = set([char for char, freq in c.items() if freq < k])
    # base case
    if len(low_freq_char) == 0:
        return len(s)
    # recursively split str into substr
    division_points = [i for i in range(len(s)) if s[i] in low_freq_char]
    substr_lst = []
    # start
    substr_lst.append(s[:division_points[0]])
    # middle
    for i in range(len(division_points) - 1):
        substr_lst.append(s[division_points[i] + 1: division_points[i + 1]])
    # end
    substr_lst.append(s[division_points[-1] + 1:])
    return max([get_longest_substring(substr, k) for substr in substr_lst])
// Solution 1: O(n^2) brute force
// time O(n^2)
// space O(1)
class Solution {
    public int longestSubstring(String s, int k) {
        if (s == null || s.isEmpty() || k > s.length()) {
            return 0;
        }
        
        int[] map = new int[26]; // letter -> freq
        int n = s.length();
        int max = 0; // length of longest substring T so far
        for (int i = 0; i < n; i++) {
            Arrays.fill(map, 0);
            for (int j = i; j < n; j++) {
                map[s.charAt(j) - 'a']++;                
                if (isValid(s, i, j, k, map)) {
                    max = Math.max(max, j - i + 1);
                }
            }
        }
        
        return max;
    }
    
    // return true if each distinct character in the substring s[left..right] appear >= k times
    private boolean isValid(String s, int left, int right, int k, int[] map) {
        int numLetters = 0; // number of distinct letters
        int numLettersAtLeastK = 0;
        for (int num : map) {
            if (num > 0) {
                numLetters++;
            }
            
            if (num >= k) {
                numLettersAtLeastK++;
            }
        }
        
        return numLettersAtLeastK == numLetters;
    }
}
/*
    https://leetcode.com/problems/longest-substring-with-at-least-k-repeating-characters/

    TC: O(26 * n) ~ O(n)
    SC: O(26)

    At a glance even though it seems like it can be solved with sliding window, it's hard to come
    up with window condition with the traditional sliding window approach.
    Problem is what will be your valid window criteria? Since we dont know how many unique chars might
    come up in the window, we dont know whether we should shrink the window or even though few of the
    unique chars have at least k instances.

    So we change the problem a bit. We change the window criteria:
    Find the max length window with atmost X unique chars. This is easier problem to deal with.
    The shrinking window criteria is clear, also we also keep track of chars in the window
    with frequency >= k while solving this problem.

    Now since we are limiting the no. of unique chars, we need to run the above |unique chars in s| times.
*/
class Solution {
public:
    int uniqueChars(string& s) {
        unordered_set<char> chars(s.begin(), s.end());
        return chars.size();
    }

    int longestSubstring(string s, int k) {
        // find the no. of unique chars in string
        int max_unique_chars = uniqueChars(s);
        int max_len = 0, n = s.size();

        for(int curr_unique_chars = 1; curr_unique_chars <= max_unique_chars; curr_unique_chars++) {
            int start = 0, end = 0;
            int atleast_k = 0;
            unordered_map<char, int> freq;

            // Process the max length window with at max curr_unique_chars unique chars
            while(end < n) {
                // attempt window expansion
                if(++freq[s[end]] == k)
                    ++atleast_k;
                ++end;

                // shrink the window if unique chars exceeds the limit
                while(freq.size() > curr_unique_chars && start <= end) {
                    // Current char contributed to atleast_k count, so it's count will be lesser than k now
                    if(freq[s[start]] == k)
                        --atleast_k;
                    if(--freq[s[start]] == 0)
                        freq.erase(s[start]);
                    ++start;
                }
                // If the current window has required no. of chars and it also each unique
                // chars have atleast k instances
                if(freq.size() == curr_unique_chars && atleast_k == freq.size())
                    max_len = max(max_len, end - start);
            }
        }
        return max_len;
    }
};
var longestSubstring = function(s, k) {
    let n = s.length;
    if(n == 0 || n < k)
        return 0;
    if(k == 1)
        return n;
    
    const freq = {};  // object to store the freq of each character ex . { 'a' : 2 , 'b' : 1 ...}
    
	// counting the freq. of each character
    for(let i=0;i<n;i++)  
    {
        let char = s[i];
        if(freq[char])    // if the character is already present , increase it's freq.
            freq[char]++;
        else
            freq[char] = 1; // else assign the freq. as 1
    }
    let i = 0;
    while(i < n && freq[s[i]] >= k)  // while loop continue till the freq. of character is greater than or equal to k
        i++;
    
    if(i >= n-1) // if i == string.length
        return i;
    
    let left1 = longestSubstring(s.substring(0,i),k);  // dividing the string at index where freq. of character is less than k and calling the func again on the substring
    
    while(i < n && freq[s[i]] < k) // ignore the char whose freq. is less than k
        i++;
    
    let right1 = longestSubstring(s.substring(i),k); // second part of the string
    
    return Math.max(left1,right1);
};
Longest Substring with At Least K Repeating Characters