How do you solve Find All Anagrams in a String on LeetCode?

Find All Anagrams in a String (LeetCode #438) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: Anagrams have the same character frequency.

What is the brute force solution for Find All Anagrams in a String?

The brute force approach for Find All Anagrams in a String is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach checks every possible substring of 's' that has the same length as 'p' to see if it is an anagram. This is straightforward but inefficient as it involves repeated checks. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Find All Anagrams in a String?

Find All Anagrams in a String uses the following concepts: Hash Table, String, Sliding Window. The recommended patterns to study are: Hash Map, Sliding Window.

What are the interview tips for Find All Anagrams in a String?

Explain your thought process clearly. Discuss time and space complexities upfront. Consider edge cases and test your solution with them.

What are common mistakes when solving Find All Anagrams in a String?

Not considering edge cases where 's' is shorter than 'p'. Confusing character frequency with sorted order.

#438

Find All Anagrams in a String

Medium

Hash TableStringSliding WindowHash MapSliding Window

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(n)

💡

Intuition

Time O(n)Space O(n)

The optimal solution uses a sliding window approach with a frequency count of characters. This way, we can efficiently check if the current window is an anagram of 'p' without sorting each time.

⚙️

Algorithm

4 steps

1Step 1: Create a frequency count for characters in 'p'.
2Step 2: Initialize a sliding window of size equal to 'p' and maintain a frequency count for the current window in 's'.
3Step 3: Slide the window across 's', updating the frequency count by adding the new character and removing the old character.
4Step 4: After each slide, compare the frequency counts. If they match, record the starting index.

solution.py16 lines

1from collections import Counter
2
3def findAnagrams(s, p):
4    p_count = Counter(p)
5    s_count = Counter(s[:len(p)])
6    result = []
7    if s_count == p_count:
8        result.append(0)
9    for i in range(len(p), len(s)):
10        s_count[s[i]] += 1
11        s_count[s[i - len(p)]] -= 1
12        if s_count[s[i - len(p)]] == 0:
13            del s_count[s[i - len(p)]]
14        if s_count == p_count:
15            result.append(i - len(p) + 1)
16    return result

ℹ

Complexity note: The time complexity is O(n) since we traverse the string 's' once while maintaining a frequency count. The space complexity is O(n) due to the storage of character counts for 'p' and the current window.

1Anagrams have the same character frequency.
2Using a sliding window allows efficient checking without repeated sorting.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.