Java O(n) Solution (HashMap + Sliding Window)


  • 1
    public List<Integer> findAnagrams(String s, String p) {
    		
    	List<Integer> indexes = new ArrayList<>();
    	if(s.isEmpty() || p.length()>s.length()) return indexes;
    	Map<Character,Integer> pHash = new HashMap<>();
    	for(char c: p.toCharArray()) {
    		if(pHash.containsKey(c)) {
    			pHash.put(c, pHash.get(c)+1);
    		} else {
    			pHash.put(c, 1);
    		}
    	}
    	
    	int numberOfCharsToBeZero = pHash.keySet().size();
    	
    	for(int i=0;i<p.length();i++) {
    		char c = s.charAt(i);
    		if(pHash.containsKey(c)) {
    			int value = pHash.get(c)-1;
    			pHash.put(c, value);
    			if(value==0) numberOfCharsToBeZero--;
    		}
    	}
    	if(numberOfCharsToBeZero==0) indexes.add(0);
    	int start=0;
    	int end=p.length()-1;
    	while(end<s.length()-1) {
    		char startChar = s.charAt(start++);
    		char endChar = s.charAt(++end);
    		if(pHash.containsKey(startChar)) {
    			if(pHash.get(startChar)==0) numberOfCharsToBeZero++;
    			pHash.put(startChar, pHash.get(startChar)+1);
    		}
    		if(pHash.containsKey(endChar)) {
    			pHash.put(endChar, pHash.get(endChar)-1);
    			if(pHash.get(endChar)==0) numberOfCharsToBeZero--;
    		}
    		if(numberOfCharsToBeZero==0) indexes.add(start);
    	}
    	return indexes;
    }
    

    Build an HashMap containing the count of each char in the p string;
    Decrement the counter of each char for each char you insert in the sliding window;
    Increment the counter of each char for each char you remove from the sliding window;
    Store the number of char with count == 0 in the hash map, so you don't have to check every time.
    If all the char have count==0, that means that the sliding window contains all the chars from the p string.


Log in to reply
 

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