Java Recursion Beat 91%


  • 0
    D
    public class Solution {
        public int longestSubstring(String s, int k) {
            char [] c = s.toCharArray();
            return find(c,k,0,c.length-1);
        }
        
        
        public int find(char [] c, int k, int lo, int hi){
            if(lo>hi)   return 0;
            if(hi-lo + 1 <k)    return 0;   // not enough length
            int [] count = new int [26];
            for(int i = lo;i<=hi;i++){
                count[c[i]-'a']++;
            }
            
            for(int i = 0;i<26;i++){
                if(count[i]<k && count[i]>0){   // not satisify, then divide into "multiple" section by this character
                    
                    // seperate by 'a' + i
                    int max = 0;
                    int left = lo;
                    
                    for(int j = lo;j<=hi;j++){
                        if(c[j]-'a' == i){
                            max = Math.max(max,find(c,k,left,j-1));
                            left = j+1;
                        }
                    }
                    max = Math.max(max,find(c,k,left,hi));
                    return max;
                }
            }
            return hi -lo +1;
        }
    }
    

Log in to reply
 

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