Find All Anagrams in a String

January 21, 2024

Problem Statement #

Given a string s and a non-empty string p, find all the start indices of p’s anagrams in s. Strings consist of lowercase English letters only and 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”, also an anagram of “abc”.

Solution Approach #

The solution uses the sliding window approach combined with a hashmap to track the frequency of characters in p and the current window in s.

Algorithm Steps #

1. Create two hashmaps to store the frequency of characters in p and the current window in s.
2. Use a sliding window of size equal to the length of p to traverse s.
3. Update the frequency of characters in the current window.
4. If the two hashmaps are equal, add the start index of the window to the result list.
5. Continue sliding the window and updating the frequency hashmap.
6. Return the list of start indices.

Code (Python) #

from collections import Counter

def findAnagrams(s, p):
    if len(p) > len(s): return []

    p_count = Counter(p)
    s_count = Counter(s[:len(p) - 1])
    result = []

    for i in range(len(p) - 1, len(s)):
        s_count[s[i]] += 1   # Add the current character to the window
        if s_count == p_count:
            result.append(i - len(p) + 1)   # Append the start index of the window
        s_count[s[i - len(p) + 1]] -= 1   # Remove the character left out of the window
        if s_count[s[i - len(p) + 1]] == 0:
            del s_count[s[i - len(p) + 1]]

    return result

# Test the function
print(findAnagrams("cbaebabacd", "abc"))  # Output: [0, 6]

Time Complexity #

O(n), where n is the length of string s. Each character in s is processed once.

Space Complexity #

O(1), as the hashmaps store a maximum of 26 English lowercase letters.