Share JAVA AC Solution (3ms)

  • 0
    public int longestSubstring(String s, int k) {
        return divide(s,0,s.length()-1,k);        
    private int divide(String s, int start, int end, int k){
        // pass impossible cases
        if(end<start) return 0;
        if(end-start+1<k) return 0;
        char[] schar = s.toCharArray();
        // count the occurence of each letter in the string from start and end;
        int[] cnt = new int[26];
        int max = 0;
        // count frequence of each character
        for(int i=start;i<=end;i++){
            int index = schar[i]-'a';
        // check if there is a letter which occurence is smaller than k
        // if there it is, divide it and rerun.
        for(int i=0;i<26;i++){
            if(cnt[i]==0) continue;
                char c = (char) (i+'a');
                int smaller = s.indexOf(c,start);
                    int left = divide(s,start,smaller-1,k);
                    int right = divide(s,smaller+1,end, k);
                    return Math.max(left, right);
                    return 0;
        return end-start+1;  // if every letter comes along more than k times

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.