LC 438. Find All Anagrams in a String

Sarthak Sehgal · May 25, 2020

medium   strings

An anagram is basically a permutation or rearrangement of the string. This allows us to identify an anagram of the string simply by the frequency map, i.e., if we know how many times each character occurs in the string. Clearly, the anagram has to have the same length as well. Idea:

  1. Since both the strings only contain lower case alphabets, define a “count” array of length 26 which initially stores count of each character in string p.
  2. Consider substrings of length(p) in string s and compare the frequency map of these substrings with the “count” array.

We don’t really need to have a different array to store the frequencies of the substrings we consider, here’s what we can do instead:

  1. When we consider the first substring, i.e., s[0...length(p)-1], iterate through it and decrease the corresponding frequency in the count array itself.
  2. Now, whenever we move to an adjacent substring, i.e., s[1..length(p)] or in general from substring s[i...i+length(p)-1] to s[i+1...i+1+length(p)-1], we increase the count of character corresponding to s[i] (since it is no langer a part of the substring) and decrease the count of character corresponding to s[i+1+length(p)-1] (since it is now a part of the substring).
  3. At each step, iterate through the count array and if all the values are 0 then it means that we have an anagram.

Note that we use a constant size count array as we know that the string contains only lower case english alphabets. If it is not known, a map (unordered) would be a better choice.

vector<int> findAnagrams(string s, string p) {
    vector<int> ans;
    int pLen = p.length(), sLen = s.length();

    if (pLen > sLen)
        return ans;

    int count[26] = {0};
    for (int i=0; i<pLen; i++) {
        count[p[i]-'a']++;
        count[s[i]-'a']--;
    }

    count[s[pLen-1]-'a']++;
    int begin = 0, end = pLen-1;

    for (;end<sLen; begin++, end++) {
        count[s[end]-'a']--;
        bool isAnagram = true;
        for (int i=0; i<26; i++)
            if (count[i])
                isAnagram = false;
        if (isAnagram)
            ans.push_back(begin);
        count[s[begin]-'a']++;
    }

    return ans;
}

Time complexity: O(length(s)). Note that iterating over count array is constant time operation as its length is fixe (=26)
Space complexity: O(1)

Twitter, Facebook