30% off Lifetime Premium Access expires December 2nd!

30% off Lifetime Premium Access expires Dec 2nd!

Your Dashboard

Interview Coaching

Mock Interviews

1:1 Mentorship

Salary Negotiation

Practice

Learn

System Design

ML System Design

Code

Behavioral

Salary Negotiation

Interview Guides

Blog

Community

Interview Questions

Interview Experiences

Peer System Design Library

Ask The Community

Discord

Refer a Friend

Pricing

Become a Coach

⌘K

Pricing Become a Coach

⌘K

Get Premium

Leetcode 438. Find All Anagrams in a String

Given strings s and p, return all start indices of substrings in s that are anagrams of p; the core challenge is to detect equal character multisets efficiently, typically via a sliding window with frequency counts (s, p up to 3×10^4, lowercase letters).

Asked at:

Amazon

DESCRIPTION

Given strings s and t, return all start indices of substrings in s that are anagrams of t; the core challenge is to detect equal character multisets efficiently, typically via a sliding window with frequency counts (s, t up to 3×10^4, lowercase letters).

Input:


s = "cbaebabacd", t = "abc"

Output:


[0, 6]

Explanation: At index 0, substring "cba" is an anagram of "abc". At index 6, substring "bac" is an anagram of "abc". These are the only two anagram matches.

Constraints:

1 <= s.length, t.length <= 3 × 10^4
s and t consist of lowercase English letters only
The output can be returned in any order

Understanding the Problem

Let's understand what we're being asked to do. We have a string s = "cbaebabacd" and a pattern t = "abc", and we need to find all starting positions in s where an anagram of t appears.

An anagram means the same characters with the same frequencies, but in any order. So "abc", "bca", "cab" are all anagrams of t.

Tracing through s: at index 0, we have "cba" (an anagram of "abc"! add 0 to result). At index 6, we have "bac" (another anagram! add 6 to result). Final answer: [0, 6].

Important constraint: Both strings contain only lowercase English letters. The pattern t has length up to 30,000, and s can be up to 30,000 characters.

Edge cases to consider: What if t is longer than s? (return empty list). What if t has duplicate characters like "aab"? What if s is empty?

Brute Force Approach

The straightforward approach is to check every possible substring of length |t| in string s. For each starting position, extract the substring and verify if it's an anagram by sorting both strings and comparing, or by counting character frequencies from scratch. If they match, add the starting index to the result. This approach is simple but inefficient because we recount characters for overlapping windows.

def find_anagrams(s, t):
    """
    Find all start indices of t's anagrams in s using brute force.
    For each possible substring of length |t|, check if it's an anagram.
    """
    result = []
    p_len = len(t)
    s_len = len(s)
    
    # Edge case: if t is longer than s, no anagrams possible
    if p_len > s_len:
        return result
    
    # Sort t once for comparison
    sorted_p = sorted(t)
    
    # Check every possible starting position
    for i in range(s_len - p_len + 1):
        # Extract substring of length p_len starting at i
        substring = s[i:i + p_len]
        
        # Sort the substring and compare with sorted t
        # This is inefficient because we sort for every window
        if sorted(substring) == sorted_p:
            result.append(i)
    
    return result

Start finding all anagrams of t in s using brute force

0 / 78

Test Your Knowledge

Complexity Analysis

Time Complexity: O(n * m) For each of the n-m+1 possible starting positions, we spend O(m) time counting or sorting characters in the window, where m is the length of pattern t

Space Complexity: O(1) We only use a fixed-size frequency array for 26 lowercase letters, regardless of input size

Building Intuition

Instead of checking every possible substring by sorting or counting characters from scratch, notice that as we move through s, we're only adding one new character and removing one old character from our window.

If we maintain a running count of characters in our current window, we can update it in constant time as we slide forward!

By maintaining character frequencies as we slide through s, we avoid recounting the entire window each time.

This transforms the problem from checking O(n) windows, each taking O(m) time to verify (total O(n*m)), into checking O(n) windows with O(1) updates (total O(n))!

Imagine you have a physical counter for each letter a-z. You set up the counters to match pattern t.

Now slide a window of size |t| through string s. At each position: add the new character entering the window (increment its counter), remove the old character leaving the window (decrement its counter). After each update, check if all counters match the pattern's counters.

The key insight: you're not recounting from scratch - you're making one addition and one subtraction per slide!

Common Mistakes

Recounting the entire window from scratch at each position instead of incrementally updating - this degrades time complexity from O(n) to O(n*m)

Forgetting to handle the initial window setup separately before starting the sliding process

Using string sorting to check anagrams (O(m log m) per check) instead of frequency comparison (O(1) for fixed alphabet)

Off-by-one errors when determining window boundaries - the window should be exactly length |t|, so valid starting positions are 0 to n-m

Not handling edge cases: when t is longer than s (return empty list), or when t or s is empty

Optimal Solution

The optimal approach uses a sliding window with character frequency counting. First, count the frequency of each character in pattern t. Then slide a window of size |t| through string s, maintaining a frequency count of characters in the current window. As the window slides, add the new character entering and remove the old character leaving in constant time. After each slide, compare the window's frequency map with the pattern's frequency map - if they match, record the starting index. This eliminates redundant recounting of overlapping characters.

def find_anagrams(s, t):
    """
    Find all start indices of anagrams of t in s using sliding window.
    """
    result = []
    
    # Edge case: if t is longer than s, no anagrams possible
    if len(t) > len(s):
        return result
    
    # Build frequency map for pattern t
    p_freq = {}
    for char in t:
        p_freq[char] = p_freq.get(char, 0) + 1
    
    # Initialize sliding window frequency map
    window_freq = {}
    window_size = len(t)
    
    # Build initial window of size len(t)
    for i in range(window_size):
        char = s[i]
        window_freq[char] = window_freq.get(char, 0) + 1
    
    # Check if initial window is an anagram
    if window_freq == p_freq:
        result.append(0)
    
    # Slide the window through string s
    for i in range(window_size, len(s)):
        # Add new character entering the window
        new_char = s[i]
        window_freq[new_char] = window_freq.get(new_char, 0) + 1
        
        # Remove old character leaving the window
        old_char = s[i - window_size]
        window_freq[old_char] -= 1
        if window_freq[old_char] == 0:
            del window_freq[old_char]
        
        # Check if current window is an anagram
        if window_freq == p_freq:
            result.append(i - window_size + 1)
    
    return result

start

Start finding all anagrams of t in s

0 / 34

Test Your Knowledge

Complexity Analysis

Time Complexity: O(n + m) We make a single pass through string s (O(n)) and initially count pattern t (O(m)). Each window update is O(1), and comparing frequency maps is O(26) = O(1) for lowercase letters

Space Complexity: O(1) We use two fixed-size frequency arrays for 26 lowercase letters, which is constant space O(26) = O(1)

What We've Learned

Sliding window with frequency map: When comparing character multisets (anagrams, permutations) in substrings, use a fixed-size sliding window with hash map frequency counts - this transforms an O(n×m) naive approach into O(n) by reusing computations as the window slides.
Window validity via counter variable: Instead of comparing two hash maps on every iteration (26 operations), maintain a matches counter tracking how many character frequencies currently match - increment/decrement it as characters enter/leave the window, checking `matches == 26` in O(1).
Add-then-remove window pattern: When sliding the window, always add the new character first, then remove the old character - this ensures the window size stays correct and prevents off-by-one errors when updating your frequency counts and match tracking.
Array vs HashMap for fixed alphabet: With only lowercase letters (26 characters), use a fixed-size array[26] instead of a HashMap - it's faster (no hashing overhead), uses less memory, and simplifies iteration when counting matches.
Anagram detection generalization: This sliding window + frequency counting pattern extends to any fixed-length substring matching problem with character constraints: permutation in string, substring with concatenation of words, or finding all substrings with exactly k distinct characters.
Real-world plagiarism detection: This technique powers fuzzy string matching in plagiarism checkers and DNA sequence analysis - detecting when text segments contain the same content in different orders, or finding gene subsequences that are permutations of target patterns.

Test Your Understanding

Why is sliding-window the right data structure for this problem?

sliding-window provides the optimal access pattern

It's the only data structure that works

It's the easiest to implement

It uses the least memory

Select an answer to see the explanation

Question Timeline

See when this question was last asked and where, including any notes left by other candidates.

Company

Level

Region

Mid October, 2024

Amazon

Senior

Find all anagrams in a string

Comments

Your account is free and you can post anonymously if you choose.

Hello Interview Premium

Recent interview questions

System Design Guided Practice

Exclusive content

Learn More

Leetcode 438. Find All Anagrams in a String

DESCRIPTION

Understanding the Problem

Brute Force Approach

Test Your Knowledge

Complexity Analysis

Building Intuition

Common Mistakes

Optimal Solution

Test Your Knowledge

Complexity Analysis

What We've Learned

Related Concepts and Problems to Practice

Test Your Understanding

Question Timeline

Comments

Questions

Learn

Links

Legal

Contact