Skip to main content

438. Find All Anagrams in a String

medium

Find all start indices of substrings in s that are anagrams of p. Classic sliding-window-with-character-counts problem — the hash-table counter is the state you slide.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Given two strings s and p, return an array of all the start indices of p's anagrams in s. You may return the answer in any order. An anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Constraints

  • 1 <= s.length, p.length <= 3 * 10^4
  • s and p consist of lowercase English letters.

Examples

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', which is an anagram of 'abc'.

Example 2

Input
s = 'abab', p = 'ab'
Output
[0,1,2]

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Fixed-size window of length p.length sliding across s. At each window position, check if the window's letter counts == p's letter counts.

Hint 2

Recomputing the count from scratch at each step is O(L) per step. Slide instead: add the new char, remove the leftmost char.

Hint 3

Comparing two length-26 count arrays each step is O(26) = O(1); total O(n).

Solution approach

Reveal approach

Build a length-26 target count from p. Maintain a window count of length 26 over s[i .. i + p.length - 1]. Initialize by counting the first p.length chars of s. If window == target, record index 0. Then slide: for i from 1 to n - p.length, decrement count for s[i - 1] (leaving the window) and increment count for s[i + p.length - 1] (entering); if window == target, record i. Return the result list. Comparing 26-entry arrays at each step is O(26) and the slide itself is O(1) per step, giving O(n) overall. A faster 'matched chars' counter avoids comparing arrays — but the array-compare version is easy to write and read and is fast enough.

Complexity

Time
O(n)
Space
O(1) — bounded by alphabet

Related patterns

  • sliding-window
  • hash-table
  • counting
  • string

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Google
  • Meta
  • Microsoft

Practice these live with InterviewChamp.AI

Drill Find All Anagrams in a String and Hash Tables problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →