Solution: Problem Challenge 2: String Anagrams

Grokking the Coding Interview: Patterns for Coding Questions

Ask Author

Back to course home

0% completed

Vote For New Content

Solution: Problem Challenge 2: String Anagrams

Table of Contents

Contents are not accessible

Problem Statement

Given a string and a pattern, find all anagrams of the pattern in the given string.

Every anagram is a permutation of a string. As we know, when we are not allowed to repeat characters while finding permutations of a string, we get $N!$ permutations (or anagrams) of a string having $N$ characters. For example, here are the six anagrams of the string abc:

Write a function to return a list of starting indices of the anagrams of the pattern in the given string.

Example 1:

Input: str="ppqp", pattern="pq"  
Output: [1, 2]  
Explanation: The two anagrams of the pattern in the given string are "pq" and "qp".

Example 2:

Input: str="abbcabc", pattern="abc"  
Output: [2, 3, 4]  
Explanation: The three anagrams of the pattern in the given string are "bca", "cab", and "abc".

Constraints:

1 <= s.length, p.length <= 3 * 10<sup>4</sup>
str and pattern consist of lowercase English letters.

Solution

To solve this problem, we use a sliding window approach along with a frequency map to keep track of character counts. By moving the window across the string, we can compare the current window's characters with the pattern's characters.

This method is efficient because it allows us to check each possible window without repeatedly recalculating character counts from scratch. The sliding window approach is chosen because it ensures that each character in the string is processed only once, making the algorithm time-efficient. Moreover, using a hash map to store character frequencies helps quickly check if a window matches the pattern.

Step-by-Step Algorithm

Initialize Variables:
- Create a windowStart to mark the start of the sliding window.
- Create a matched variable to track the number of characters matched with the pattern.
- Create a charFrequencyMap to store the frequency of each character in the pattern.
- Create a resultIndices list to store the starting indices of the anagrams found.
Build Character Frequency Map:
- Loop through each character in the pattern and update charFrequencyMap with the count of each character.
Slide the Window:
- Loop through the string with windowEnd marking the end of the sliding window.
- Check if the current character at windowEnd is in the charFrequencyMap.
  - If it is, decrement its frequency in the map.
  - If the frequency becomes zero, increment the matched variable.
Check for Anagram:
- If matched equals the size of charFrequencyMap, it means an anagram is found. Add windowStart to resultIndices.
Shrink the Window:
- If the window size exceeds the pattern length, move the windowStart to the right.
- Restore the frequency of the character at windowStart in charFrequencyMap.
- If the restored frequency was zero, decrement the matched variable.

Algorithm Walkthrough

Let's take the example where str = "abbcabc" and pattern = "abc".

Initialize:
- windowStart = 0
- matched = 0
- charFrequencyMap = {'a': 1, 'b': 1, 'c': 1}
- resultIndices = []
Window Slide:
- windowEnd = 0, rightChar = 'a'
  - charFrequencyMap = {'a': 0, 'b': 1, 'c': 1}
  - matched = 1
- windowEnd = 1, rightChar = 'b'
  - charFrequencyMap = {'a': 0, 'b': 0, 'c': 1}
  - matched = 2
- windowEnd = 2, rightChar = 'b'
  - charFrequencyMap = {'a': 0, 'b': -1, 'c': 1}
  - matched remains 2
  - Since windowEnd - windowStart + 1 (3) is equal to the length of the pattern, we need to shrink the window.
  - windowStart = 0, leftChar = 'a'
    - charFrequencyMap = {'a': 1, 'b': -1, 'c': 1}
    - matched becomes 1
    - Increment windowStart to 1.
Continue Sliding:
- windowEnd = 3, rightChar = 'c'
  - charFrequencyMap = {'a': 1, 'b': -1, 'c': 0}
  - matched = 2
  - Since windowEnd - windowStart + 1 (3) is equal to the length of the pattern, we need to shrink the window.
  - windowStart = 1, leftChar = 'b'
    - charFrequencyMap = {'a': 1, 'b': 0, 'c': 0}
    - matched remains 2
    - Increment windowStart to 2.
Further Sliding:
- windowEnd = 4, rightChar = 'a'
  - charFrequencyMap = {'a': 0, 'b': 0, 'c': 0}
  - matched = 3
  - Add windowStart = 2 to resultIndices
  - windowStart = 2, leftChar = 'b'
    - charFrequencyMap = {'a': 0, 'b': 1, 'c': 0}
    - matched = 2
    - Increment windowStart to 3.
Final Slide:
- windowEnd = 5, rightChar = 'b'
  - charFrequencyMap = {'a': 0, 'b': 0, 'c': 0}
  - matched = 3
  - Add windowStart = 3 to resultIndices
  - windowStart = 3, leftChar = 'c'
    - charFrequencyMap = {'a': 0, 'b': 0, 'c': 1}
    - matched = 2
    - Increment windowStart to 4.
- windowEnd = 6, rightChar = 'c'
  - charFrequencyMap = {'a': 0, 'b': 0, 'c': 0}
  - matched = 3
  - Add windowStart = 4 to resultIndices
  - windowStart = 4, leftChar = 'a'
    - charFrequencyMap = {'a': 1, 'b': 0, 'c': 0}
    - matched = 2
    - Increment windowStart to 5.
Result:
- resultIndices = [2, 3, 4]

Code

Here is what our algorithm will look like:

Python3

. . . .

Complexity Analysis

Time Complexity

Creating the frequency map: The algorithm first creates a frequency map of the characters in the pattern. This step takes $O(M)$ time, where M is the length of the pattern.
Sliding window traversal: The algorithm uses a sliding window approach to traverse through the string. The outer loop runs for each character in the string, so the loop runs $O(N)$ times, where N is the length of the input string.
Character frequency updates: For each character in the window, the algorithm performs constant-time operations like updating the frequency in the charFrequencyMap and adjusting the matched count. These operations take $O(1)$ time on average, as hash map operations like put() and get() are constant on average.
Therefore, the total time complexity is $O(N + M)$ , where N is the length of the input string and M is the length of the pattern.

Overall time complexity: $O(N + M)$ .

Space Complexity

HashMap space: The algorithm uses a hash map, charFrequencyMap, to store the frequency of characters in the pattern. This requires $O(M)$ space, where M is the number of unique characters in the pattern.
Result list: The result list stores the starting indices of all anagrams found in the input string. In the worst case, all substrings of the string could be an anagram, so this would require space proportional to $O(N)$ to store the result indices.
Additional variables: The algorithm uses a few extra variables (windowStart, windowEnd, matched), all of which require constant space, $O(1)$ .

Overall space complexity: $O(M + N)$ , where M is the number of unique characters in the pattern, and N is the number of result indices that may be stored.

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible