4ms divide and conqure


  • 0
    public class Solution {
    	    public int longestSubstring(String s, int k) {
    	    	if(k == 0 || s.length() < k) return 0;
    	    	int res = 0;
    	    	int[] table = new int[26];
    	    	boolean is = true;
    	        for(char c : s.toCharArray()) table[c-'a']++;
    	        for(int i = 0; i < 26; i++){
    	        	//not this substring
    	        	if(table[i] > 0 && table[i]<k){
    	        		is = false;
    	        		int begin = 0;
    	        		//for the first not k times repeating char
    	        		for(int j = 0 ; j <= table[i]; j++){
    	        			int index = s.indexOf(i+'a',begin);
    	        			if(index == -1) index = s.length();
    	        			res = Math.max(res, longestSubstring(s.substring(begin,index),k));
    	        			begin = index + 1;
    	        		}
    	        		break;
    	        	}
    	        }
    	        return is ? s.length() : res;
    	    }
    }
    

Log in to reply
 

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