Find All Anagrams in a String

Given a stringsand 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:

It's ok to solve it by using method in Valid Anagram. However, the run time will be n^2. We can solve this problem by using sliding window method. As we iterate through source string, maintain a window of size p.length(), and count how many characters are matched with p. If the counter is equal to the size of p, we return the head index of the window. We also have to maintain the character table of string p, as the window size exceed (equal) to the length of p, we must add the head character back to the character table, and decrement the counter if necessary.

public List<Integer> findAnagrams(String s, String p) {
    List<Integer> results = new ArrayList<>();
    if (s == null || s.length() < p.length()) {
        return results;
    }
    int[] charTable = new int[26];
    for (char c : p.toCharArray()) {
        charTable[c - 'a'] ++;
    }
    int size    = p.length(), 
        head    = 0, 
        tail    = 0, 
        counter = 0;
    while (tail < s.length()) {
        if (charTable[s.charAt(tail) - 'a'] > 0) {
            counter++;
        }
        charTable[s.charAt(tail) - 'a']--;
        tail++;
        if (counter == size) {
            results.add(head);
        }
        if (tail - head == size) {
            if (charTable[s.charAt(head) - 'a'] >= 0) {
                counter--;
            }
            charTable[s.charAt(head) - 'a']++;
            head++;
        }
    }
    return results;
}