438. Find All Anagrams in a String

Problem Description

The task is to find all the starting indices of substrings in string s that are anagrams of string p. An anagram is a rearrangement of letters in a word to form a new word, using all the original letters exactly once. The two input strings, s and p, contain only lowercase English letters. The output should be a list of indices, and these indices don't need to be in any specific order.

For example, if s is "cbaebabacd" and p is "abc", then the function should return [0, 6], since the substrings starting at indices 0 ("cba") and 6 ("bac") are anagrams of "abc".

Intuition

The intuition behind the solution is to use a sliding window approach combined with character counting. The idea is to maintain a window of length equal to the length of p and slide it across s, while keeping track of the frequency of characters within the window and comparing it to the frequency of characters in p. If at any point the frequency counts match, we've found an anagram and can record the starting index of the window.

To implement this efficiently, we use two Counter objects (from Python's collections module) to store the frequency counts for p and for the current window in s. The key steps in the algorithm are as follows:

1. If s is shorter than p, immediately return an empty list as no anagrams could exist.
2. Create a Counter for string p which holds the count of each character.
3. Also, create a Counter for the first window of size len(p) - 1 in s.
4. Iterate through s starting at the index where the first full window would begin. For each index i:
   • Increment the count of character s[i] in the current window counter.
   • Check if the current window's character counts match those of p. If they do, append the starting index of the window (i - len(p) + 1) to the result list.
   • Decrement the count of character s[i - len(p) + 1] in the current window counter, effectively sliding the window one position to the right.
5. After the loop, return the list of starting indices, which contains all the starting points of anagram substrings within s.

Learn more about Sliding Window patterns.

Solution Approach

The solution approach utilizes a sliding window algorithm combined with character frequency counting.

Sliding Window Algorithm

The sliding window algorithm is quite efficient for problems that require checking or computing something among all substrings of a given size within a larger string. This technique involves maintaining a window that slides across the data to examine different subsections of it.

In this problem, we slide a window of length len(p) across the string s and at each step, we compare the frequency of characters within the window to the frequency of characters in p.

Character Frequency Counting

To track the characters' frequencies efficiently, we use Python's Counter class from the collections module. A Counter is a dictionary subclass that allows us to count hashable objects. The elements are stored as dictionary keys, and the counts of the objects are stored as the values.

Here's how the code implements the above techniques:

1. We create a Counter called cnt1 for the string p, which will remain constant throughout the algorithm.
2. Initialize a second Counter called cnt2 for the first len(p) - 1 characters of string s. We start with one less than len(p) because we will be adding one character to the counter in the main loop, effectively scanning windows of size len(p).

1cnt1 = Counter(p)
2cnt2 = Counter(s[: len(p) - 1])

3. The main loop starts from index len(p) - 1 and iterates until the end of the string s. In each iteration, we:

   • Include the next character in the current window's count by incrementing cnt2[s[i]].
   • Check if cnt1 and cnt2 are equal, which means we found an anagram. If they are equal, we append i - len(p) + 1 to our answer list ans.
   • Before moving to the next iteration, we decrement the count of the character at the start of the current window since the window will shift to the right in the next step.

1for i in range(len(p) - 1, len(s)):
2    cnt2[s[i]] += 1
3    if cnt1 == cnt2:
4        ans.append(i - len(p) + 1)
5    cnt2[s[i - len(p) + 1]] -= 1

Notice how the algorithm elegantly maintains the window size by incrementing the end character count and decrementing the start character count in each iteration, making the time complexity for this operation O(1), assuming that the inner workings of the Counter object and comparing two Counters take constant time on average.

By employing the sliding window technique and frequency counting, we avoid the need to re-compute the frequencies from scratch for each window, thereby achieving an efficient solution.

Example Walkthrough

Let's consider a small example to illustrate how the sliding window approach and character frequency counting is applied in the implementation.

Suppose our string s is "abab" and our pattern string p is "ab". We want to find all starting indices of substrings in s that are anagrams of p.

Following the steps described in the solution approach:

1. Since s is not shorter than p, we proceed with creating a Counter object for p.

1cnt1 = Counter("ab")  # This will hold {'a': 1, 'b': 1}

2. Next, initialize a Counter object for the first len(p) - 1 characters of s. In our case, the initial window will be of size 1 (2-1).

1cnt2 = Counter(s[:1])  # This will hold {'a': 1}

3. Now, we will iterate from index 1 to the length of s.

   • For index 1, we include character 'b' in cnt2 and increment its count.

   • We compare cnt1 with cnt2. Since at this point cnt1 is {'a': 1, 'b': 1} and cnt2 is {'a': 1, 'b': 1}, they are equal, which indicates that we have found an anagram starting at index 0.

   • The list ans will now include this index:

1ans = [0]

1- Before moving to the next index, we decrement the count of the character at the start of the current window (which is 'a') in `cnt2`.

4. At index 2, we include character 'a' in cnt2 then repeat the steps. cnt1 and cnt2 will still be equal, so we add index 1 to ans.

1ans = [0, 1]

1- Decrement the count of 'b' in `cnt2` before the next iteration.

5. At index 3, we include character 'b' in cnt2. The Counters are still equal, add index 2 to ans.

1ans = [0, 1, 2]

1- Finally, decrement the count of 'a' in `cnt2` as the loop is completed.

6. Since we have no more characters in s to iterate through, we have completed our search. The list ans now contains all the starting indices of the anagrams of p in s.

The final output for our example s = "abab" and p = "ab" is [0, 1, 2], indicating that anagrams of p start at indices 0, 1, and 2 in s.

Solution Implementation

Time and Space Complexity

The time complexity of the given code snippet is O(m + n), where m is the length of string s and n is the length of string p. Here's a breakdown of the complexity:

• Initializing cnt1 and cnt2 takes O(n) time because we are counting characters in strings of length n and n - 1, respectively.
• The for loop runs from n - 1 to m, resulting in O(m - n + 1) iterations.
• Inside the loop, we increment the count of s[i] in O(1) time, compare cnt1 and cnt2 in O(1) time assuming the alphabet is fixed and thus the Counter objects have a constant number of keys, and decrement the count of a character in O(1) time.
• Therefore, loop operations have a complexity of O(m - n + 1), and setting up the Counter objects has O(n), resulting in a total time complexity of O(n + m - n + 1) which simplifies to O(m + n).

The space complexity is O(1) or O(k) where k is the size of the character set (e.g., the alphabet size), assuming the alphabet is fixed and does not grow with n or m. This is because the space that cnt1 and cnt2 take up does not depend on the length of s or p but only on the number of distinct characters, which is constant for a fixed alphabet.

Learn more about how to find time and space complexity quickly using problem constraints.