In this Leetcode Longest Substring with At Least K Repeating Characters problem solution, you have 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.

Leetcode Longest Substring with At Least K Repeating Characters problem solution


Problem solution in Python.

class Solution(object):
    def longestSubstring(self, s, k):
        if len(s) < k or k == 0:
            return 0
        count = collections.defaultdict(int)
        for c in s:
            count[c] += 1
        ranges = []
        begin = end = 0
        while end < len(s):
            if count[s[end]] < k:
                if end - begin >= k:
                    ranges.append((begin, end))
                begin = end + 1
            end += 1
        if end - begin >= k:
            ranges.append((begin, end))
        if len(ranges) == 1 and end-begin == len(s):
            return end - begin
        maxLen = 0
        for i, j in ranges:
            maxLen = max(maxLen, self.longestSubstring(s[i:j], k))
        return maxLen



Problem solution in Java.

class Solution {
    public int longestSubstring(String s, int k) {
        return helper(s, k, 0, s.length() - 1);
    }
    
    private static int helper(String s, int k, int lo, int hi){
        if (lo > hi) return 0;
        HashMap<Character, Integer> repeatNum = new HashMap<Character, Integer>();
        for(int i = lo; i <= hi; i++){
            int val = repeatNum.containsKey(s.charAt(i)) ? repeatNum.get(s.charAt(i)) + 1 : 1;
            repeatNum.put(s.charAt(i), val);
        }
        HashMap<Character, Integer> lessK = new HashMap<>();
        for(char ch : repeatNum.keySet()){
            if(repeatNum.get(ch) < k){
                lessK.put(ch, repeatNum.get(ch));
            }
        }       
        
        for(char ch : lessK.keySet()){
            int midLeft = s.indexOf(ch, lo);
            int midRight = midLeft;
            for(int i = midLeft + 1; i <= hi; i++){
                if(s.charAt(i) == s.charAt(midLeft))    midRight++;
                else    break;
            }
            return Math.max(helper(s, k, lo, midLeft - 1), helper(s, k, midRight + 1, hi));
        }
        return hi - lo + 1;
    }
}


Problem solution in C++.

class Solution {
public:
    int longestSubstring(string s, int k) {
        vector<int> vocab(26,0);
        for(auto ch : s){
            ++vocab[ch-'a'];
        }
        vector<int> cands;
        for(int i=0; i<s.size(); ++i){
            if(vocab[s[i]-'a']<k){
                cands.emplace_back(i);
            }
        }
        if(cands.empty()) return s.size();
        cands.emplace_back(s.size());
        int start = 0;
        int longest = 0;
        for(auto cand : cands){
            if(cand-start>=k){
                longest = max(longestSubstring(s.substr(start,cand-start),k),longest);
            }
            start = cand+1;
        }
        return longest;
    }
};


Problem solution in C.

void subroutine(char* s, int k, int first, int last, int* ans) {
    if ( first < 0 || first > last) { return; }
    int* temp = calloc(26, sizeof(int));
    int flag = 0;
    for (int i = first; i < last + 1; i++) {
        temp[s[i] - 'a'] += 1;
    }
    while (first < last && temp[s[first] - 'a'] < k) {
        first++;
    }
    int begin = first, end = 0; ;
    for ( end = first; end <= last; end++) {
        if (temp[s[end] - 'a'] < k) {            
            subroutine(s, k, begin, end - 1, ans);
            begin = end + 1;
            flag = 1;
            break;
        }
    }
    if (flag == 0 ) {
        if (*ans < last - first + 1) {
            *ans = last - first + 1;
        }
        return;
    } 
    subroutine(s, k, begin, last, ans);

}


int longestSubstring(char * s, int k){
    int len = strlen(s);
    int* ans = calloc(1,sizeof(int));
    subroutine(s, k, 0, len-1, ans);
    return *ans;
}