All Anagrams

Find all occurrence of anagrams of a given string s in a given string l. Return the list of starting indices.

Assumptions

• sh is not null or empty.

• lo is not null.

Examples

• l = "abcbac", s = "ab", return [0, 3] since the substring with length 2 starting from index 0/3 are all anagrams of "ab" ("ab", "ba").

Solution: HashMap + sliding window

size of window = size of target string

use hashmap to track chars in target string. If both found, add starting index to result

public class Solution {
  public List<Integer> allAnagrams(String sh, String lo) {
    List<Integer> result = new ArrayList<>();
    if (lo.length() == 0) return result;
    if (sh.length() > lo.length()) return result;
    
    //count amount of each char in shorter string
    Map<Character, Integer> map = countMap(sh); 
    
    //track number of target chars found
    int match = 0; 
    
    for (int i = 0; i < lo.length(); i++){
      char tmp = lo.charAt(i);
      Integer count = map.get(tmp);
      
      //if char in target string
      if (count != null){
        map.put(tmp, count - 1);
        
        //if first sighting, dedup
        if (count == 1){
          match++;
        }
      }
      
      //add char exiting window back
      if (i >= sh.length()){
        
        //char to add back
        tmp = lo.charAt(i - sh.length());
        count = map.get(tmp);
        
        //if in target string
        if (count != null){
        
          //dedup, negative if adajacent target chars
          //ex: "aa" for target "ab"
          //count would be -1
          
          //char only exiting window if only one left in window
          //aka count == 0
          if (count == 0){
            match--;
          }
          map.put(tmp,count + 1);
        }
      }

      if (match == map.size()){
        result.add(i - sh.length() + 1);
      }
    }
    return result;
  }

  private Map<Character, Integer> countMap(String s){
    Map<Character, Integer> map = new HashMap<>();
    for (char ch: s.toCharArray()){
      Integer count = map.get(ch);
      if (count == null){
        map.put(ch, 1);
      } else {
        map.put(ch, count + 1);
      }
    }
    return map;
  }
}