Java solution using 3 HashMaps


  • 0
    Q

    I use 1st hashamp to keep track of how many of each character is required.
    2nd hashmap is originally the copy of first hashmap. In first iteration we decrement from second hashmap whenever a matching character is found, if 2nd hashmap size reaches 0 we know that a substring containing all chars exist, and we have the end index for the first interval.
    3rd HashMap is used to keep track of how many of each character is encoutered. We update character counts as we iterate over (s), and update start/end pointer positions. We move start pointer when we have all the required charcters in 3rd hashmap otherwise we move end pointer.

    public String minWindow(String s, String t) {
            HashMap<Character, Integer> template = new HashMap<Character, Integer>();
            for (char c:t.toCharArray()){
            	template.put(c, template.containsKey(c)?template.get(c)+1:1);
            }
            Map<Character, Integer> countdown = (Map<Character, Integer>)template.clone();
            HashMap<Character, Integer> totals = new HashMap<Character, Integer>();
            int endIndex = 0;
            for (int i=0;i<s.length();i++){
            	char c = s.charAt(i);
            	if (template.containsKey(c)){
            		Integer count = countdown.get(c);
            		if (count!=null){
            		    if (count == 1){
            		        countdown.remove(c);
            		    }
            		    else{
                			countdown.put(c, count-1);
            		    }
            		}
            		totals.put(c, totals.get(c)==null?1:totals.get(c)+1);
            		if (countdown.isEmpty()){
            			endIndex = i+1;
            			break;
            		}
            	}
            }
            if (endIndex > 0){
                int startStringIndex =0;
                int endStringIndex = endIndex;
                for (int i=0;i<s.length();i++){
                	char c = s.charAt(i);
                	int l = i+1;
                	if (template.containsKey(c)){
                		if (totals.get(c)>template.get(c)){
                			totals.put(c, totals.get(c)-1);
                			if (endIndex-l < endStringIndex-startStringIndex){
                				endStringIndex = endIndex;
                				startStringIndex = l;
                			}
                		}
                		else{
                			boolean found = false;
                			for (int j=endIndex;j<s.length();j++){
                				char cj = s.charAt(j);
            					if (cj == c){
            						endIndex = j+1;
            						found = true;
            						break;
            					}
            					else if (template.containsKey(cj)){
            						totals.put(cj,  totals.get(cj)+1);
            					}
                			}
                			if (!found){
                			     return s.substring(startStringIndex,endStringIndex);
                			}
                		}
                	}
                	else if (endIndex-l < endStringIndex-startStringIndex){
        			   	endStringIndex = endIndex;
        				startStringIndex = l;
        			}
                }
                return s.substring(startStringIndex,endStringIndex);
            }
            return "";
    	}

Log in to reply
 

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