Java Solution with Array, HashMap and Math tricks


  • 1
    Z
    public boolean findStart = false;
    public int start = 0;
    public int end = 0;
    public int longestSubstring(String s, int k) {
    	int result = 0;
    	int[] a = new int[s.length()];
    	int[] b = new int[s.length()];
    	int[] c = new int[s.length()];
    	
    	int[] memA = new int[256];
    	for(int i = 0; i < a.length; i++){
    		memA[s.charAt(i)]++;
    		a[i] = memA[s.charAt(i)];
    	}
    	
    	int[] memB = new int[256];
    	for(int i = b.length - 1; i >= 0; i--){
    		memB[s.charAt(i)]++;
    		b[i] = memB[s.charAt(i)];	
    	}
    
    	for(int i = 0; i < a.length; i++){
    		c[i] = a[i] + b[i];
    	}
    	//build c array
    
    	
    	for(int i = 0; i < c.length; i++){		
    		//if c[i] is qualified
    		if(c[i] >= k + 1){
    			//reset start pointer
    			if(findStart == false){
    				start = i;
    				findStart = true;
    			}
    			//extreme situation such as"aaaaa...."
    			end = i;
    			//fix the end situation
    			if(i == c.length - 1){
    				if(end - start + 1 >= k){
    					return Math.max(result, getResult(c, s, start, end, k));
    				}
    			}
    		}
    		//if c[i] is not qualified
    		else if(c[i] < k + 1){
    			//cutting branch, for example "abbbbb...b"
    			if(i > 0 && s.charAt(i) == s.charAt(i - 1)){
    				continue;
    			}
    			//set end pointer
    			if(i > 0 && c[i - 1] >= k + 1){
    				//make sure the previous number is qualified
    				end = i - 1;
    			}
    			if(i != 0 && end - start + 1 >= k){
    				result = Math.max(result, getResult(c, s, start, end, k));
    			}
    			//result findStart pointer each time after calculation
    			findStart = false;
    		}
    	}
    	return result;
    }
    //calculate the tmp result
    private int getResult(int[] c,String s,int start, int end, int k){
    	int result = 0;    	
    
    	//add qualified c[i] to the map
    	Map<Character, Integer> map = new HashMap<>();
    	for(int i = start; i <= end; i++){
    		if(!map.containsKey(s.charAt(i))){
    			map.put(s.charAt(i), 1);
    		}
    		else{
    			map.put(s.charAt(i), map.get(s.charAt(i)) + 1);
    		}
    	}
    
    	for(int j = end; j >= start; j--){
    		if(!map.containsKey(s.charAt(j))){
    			continue;
    		}
    		//if c[i] is not qualified
    		if(map.get(s.charAt(j)) < k){ 
    			map.remove(s.charAt(j));
    			if(map.isEmpty()){
    				return 0;
    			}
    			//fix the last k, avoid out of bound
    			if(j == s.length() - 1){
    				return getResult(c, s, start, end - 1, k);
    			}
    			//cut the selected array from the end, "bbbbbbbcded"
    			if(map.get(s.charAt(j + 1)) == null){
    				return getResult(c, s, start, end - 1, k);
    			}
    			//cut the selected array from the beginning, "abbbbbbb"
    			else{
    				return getResult(c, s, start + 1, end, k);
    			}
    		}
    		//if c[i] is qualified
    		else{//map.get(c[j] >= k)	
    			//fix the bound
    			if(j == start){
    				return end - start + 1;
    			}
    		}
    	}
    	return result;			
    }

Log in to reply
 

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