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

Assumptions

• s is not null or empty.
• l 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: 用sliding window + hashmap，先用hashmap记录s中所有字符，再对l sliding window：进入一个hashmap有的字符，并且count从1变为0时，match++；减去一个hashmap有的字符，并且count从0变为1时，match--。match == hashmap.size()时，是anagram。不用管hashmap没有的字符。

  List<Integer> allAnagrams(String s, String l) {

    if (s.length() == 0 || l.length() == 0 || l.length() < s.length()) {
      return new ArrayList<Integer>();
    }
    Map<Character, Integer> hashmap = new HashMap<>();
    for (int i = 0; i < s.length(); i++) {
      char c = s.charAt(i);
      hashmap.put(c, hashmap.containsKey(c) ? hashmap.get(c) + 1 : 1);
    }
    int match = 0;
    List<Integer> ans = new ArrayList<>();
    for (int i = 0; i < l.length(); i++) {
      char c = l.charAt(i);
      Integer count = hashmap.get(c);
      if (count != null) {
        hashmap.put(c, count - 1);
        //count从1变为0时，说明个数凑满，match++
        if (count == 1) {
          match++;
        }
      }
      if (i >= s.length()) {
        char c2 = l.charAt(i - s.length());
        count = hashmap.get(c2);
        if (count != null) {
          hashmap.put(c2, count + 1);
          //count从0变为1时，说明个数从凑满变为缺一个，match--
          if (count == 0) {
            match--;
          }
        }
      }
      if (match == hashmap.size()) {
        ans.add(i - s.length() + 1);
      }
    }
    return ans;

  }

Similar problem: Given two strings s1 and s2, write a function to return true if s2 contains the permutation of s1. In other words, one of the first string's permutations is the substring of the second string.