Divide and Conquer

Longest Substring with At Least K Repeating Characters

Find the length of the longest substring T of a given string (consists of lowercase letters only) such that every character in T appears no less thanktimes.

public class Solution {
    public int LongestSubstring(string s, int k) {
        return dac(s, 0, s.Length-1, k);
    }

    public int dac(string s, int start, int end, int k){
        if(end - start+1 <k) return 0;
        var counts = new int[26];
        for(var i=start;i<=end;i++){
            counts[s[i] - 'a']++;
        }
        for(var j=0;j<26;j++){
            if(counts[j]>0 && counts[j]<k){
                for(var i=start;i<=end;i++){
                    if(s[i] == j+'a'){
                        var l = dac(s, start, i-1, k);
                        var r = dac(s, i+1, end, k);
                        return Math.Max(l,r);
                    }
                }
            }
        }
        return end - start +1;
    }
}