Find All Anagrams in a String

Given a string s and a non-empty string p, find all the start indices of p's anagrams in s.

Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100.

The order of output does not matter.

Example 1:

Input:
s: "cbaebabacd" p: "abc"

Output:
[0, 6]

Explanation:
The substring with start index = 0 is "cba", which is an anagram of "abc".
The substring with start index = 6 is "bac", which is an anagram of "abc".

Example 2:

Input:
s: "abab" p: "ab"

Output:
[0, 1, 2]

Explanation:
The substring with start index = 0 is "ab", which is an anagram of "ab".
The substring with start index = 1 is "ba", which is an anagram of "ab".
The substring with start index = 2 is "ab", which is an anagram of "ab".

This is a quite easy problem, except... it's easy to exceed time limit. One way to optimize is to calculate the first substring in s with length of p, i.e., s.substring(0, p.length()), check if they are anagrams, if they are, add 0 to result. Then we go with a sliding window manner, we add one char to the substring, and remove one char from it. After this operation, we compare if the substrings are anagrams.

public List<integer> findAnagrams(String s, String p) {
        List<integer> rst = new ArrayList<>();
        int lenS = s.length();
        int lenP = p.length();
        if (lenS == 0 || lenP == 0 || lenS < lenP) {
            return rst;
        }
        Map<character, integer> pCounter = new HashMap<>();
        Map<character, integer> sCounter = new HashMap<>(pCounter);
        for (int i = 0; i < lenP; i++) {
            char c1 = p.charAt(i);
            char c2 = s.charAt(i);
            pCounter.put(c1, pCounter.containsKey(c1) ? pCounter.get(c1) + 1 : 1);
            sCounter.put(c2, sCounter.containsKey(c2) ? sCounter.get(c2) + 1 : 1);
        }

        if (pCounter.equals(sCounter)) {
            rst.add(0);
        }

        for (int i = lenP; i < lenS; i++) {
            char c2 = s.charAt(i - lenP);
            if (sCounter.get(c2) == 1) {
                sCounter.remove(c2);
            } else {
                sCounter.put(c2, sCounter.get(c2) - 1);
            }
            char c1 = s.charAt(i);
            sCounter.put(c1, sCounter.containsKey(c1) ? sCounter.get(c1) + 1 : 1);
            if (pCounter.containsKey(c1) && pCounter.equals(sCounter)) {
                rst.add(i - lenP + 1);
            }
        }
        return rst;
    }