Find All Anagrams in a String

Problem

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".

Solution

Sliding Window with Super Concise Code: O(n) time

public class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> res = new ArrayList<>();
        if (s == null || p == null || s.length() < p.length()) return res;
        int[] hashP = new int[256];
        for (char c : p.toCharArray()) hashP[c]++;
        int left = 0, right = 0, count = p.length();
        while (right < s.length()) {
            if (hashP[s.charAt(right++)]-- > 0) count--;
            if (count == 0) res.add(left);
            if (right - left == p.length() && hashP[s.charAt(left++)]++ >= 0) count++; //>=0 means it exists in p 
        }
        return res;
    }
}

Analysis

The solution above uses Sliding Window
We have two var left and right to check through the string s
We first move the right and decrease hashP with index s.charAt(right)
If the result is > 0, which means the character exists in hashP
We update count--
Then as long as the count == 0 we know we find an anagram so that we add left to our result
If the size of window right - left == p.length(), we recover the hashP with index left++
If the result >= 0, we know that that character originally exists in hashP
Otherwise it won't go below than 0, hence we recover count++