Algorithm of Two Pointer (Sliding Windows) to 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”.

Anagrams are strings with same characters set as frequencies and maybe in different order. We could easily write a O(MN) time solution where M and N are the length for the string and substring respectively.

Two Pointer – Sliding Window Algorithm to Find Anagrams

A better solution is to use a two pointer which forms a sliding window. As the both given strings are lowercase, thus we can record the number of frequencies in an array of fixed size – 26. We can have a O(1) function to check if two frequencies tables are equal.

Next, at each iteration, we need to update the frequency table by entering the current character and removing the first character. We then compare it with the frequency table of the substring and if there is a match, we push the index to the result set.

The follwoing is the C++ implementation of using two pointer that runs at O(N) time – with O(1) space complexity (excluding the return vector storage).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        if (p.size() > s.size()) return {};
        int freq1[26] = { 0 };
        int freq2[26] = { 0 };
        for (int i = 0; i < p.size(); ++ i) {
            char n = s[i];
            freq1[n - 'a'] ++;
        }
        for (const auto &n: p) {
            freq2[n - 'a'] ++;
        }
        vector<int> r;                
        if (equal(freq1, freq2)) { // anagrams at index 0
            r.push_back(0);
        }
        for (int i = p.size(); i < s.size(); ++ i) {
            freq1[s[i] - 'a'] ++; // new character
            freq1[s[i - p.size()] - 'a'] --; // remove the first character
            if (equal(freq1, freq2)) {
                r.push_back(i - p.size() + 1);
            }
        }
        return r;
    }
 
    // O(1) to check if two frequency table matches.    
    bool equal(int *freq1, int *freq2) {
        for (int i = 0; i < 26; ++ i) {
            if (freq1[i] != freq2[i]) return false;
        }
        return true;
    }
};

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        if (p.size() > s.size()) return {};
        int freq1[26] = { 0 };
        int freq2[26] = { 0 };
        for (int i = 0; i < p.size(); ++ i) {
            char n = s[i];
            freq1[n - 'a'] ++;
        }
        for (const auto &n: p) {
            freq2[n - 'a'] ++;
        }
        vector<int> r;                
        if (equal(freq1, freq2)) { // anagrams at index 0
            r.push_back(0);
        }
        for (int i = p.size(); i < s.size(); ++ i) {
            freq1[s[i] - 'a'] ++; // new character
            freq1[s[i - p.size()] - 'a'] --; // remove the first character
            if (equal(freq1, freq2)) {
                r.push_back(i - p.size() + 1);
            }
        }
        return r;
    }

    // O(1) to check if two frequency table matches.    
    bool equal(int *freq1, int *freq2) {
        for (int i = 0; i < 26; ++ i) {
            if (freq1[i] != freq2[i]) return false;
        }
        return true;
    }
};

We can easily count the frequency using collections.Counter in Python – which returns a Dictionary.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        if len(p) > len(s):
            return []
        freq1 = collections.Counter(s[:len(p)])
        freq2 = collections.Counter(p)
        r = []
        if freq1 == freq2:
            r.append(0)
        i = len(p)
        while i < len(s):  
            if s[i] in freq1:
                freq1[s[i]] += 1
            else:
                freq1[s[i]] = 1
            freq1[s[i - len(p)]] -= 1
            if freq1[s[i - len(p)]] == 0:
                del freq1[s[i - len(p)]]
            if freq1 == freq2:
                r.append(i - len(p) + 1)
            i += 1
        return r            

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        if len(p) > len(s):
            return []
        freq1 = collections.Counter(s[:len(p)])
        freq2 = collections.Counter(p)
        r = []
        if freq1 == freq2:
            r.append(0)
        i = len(p)
        while i < len(s):  
            if s[i] in freq1:
                freq1[s[i]] += 1
            else:
                freq1[s[i]] = 1
            freq1[s[i - len(p)]] -= 1
            if freq1[s[i - len(p)]] == 0:
                del freq1[s[i - len(p)]]
            if freq1 == freq2:
                r.append(i - len(p) + 1)
            i += 1
        return r            

–EOF (The Ultimate Computing & Technology Blog) —