Share JAVA AC Solution (3ms)


  • 0
    M
    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';
            cnt[index]++;
        }
        
        // 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;
            if(cnt[i]<k){
                char c = (char) (i+'a');
                int smaller = s.indexOf(c,start);
                if(smaller>=0){
                    int left = divide(s,start,smaller-1,k);
                    int right = divide(s,smaller+1,end, k);
                    return Math.max(left, right);
                }else{
                    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.