Find All Anagrams in a String
The key idea
Two strings are anagrams when their letter frequency counts are identical. Slide a fixed-width window of length
len(p) across s and keep its running letter count. The window matches whenever its count vector equals p's count vector, so you never re-scan a substring from scratch — each step just adds the entering letter and drops the leaving one.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^4sandpconsist of lowercase English letters
Examples
Input: s = "cbaebabacd", p = "abc"
Output: [0,6]
Input: s = "abab", p = "ab"
Output: [0,1,2]
Complexity
Time: O(n) Space: O(1)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More Sliding Window problems
- Longest Continuous Increasing SubsequenceEASY
- Longest Repeating Character ReplacementMEDIUM
- Longest Subarray of 1's After Deleting One ElementMEDIUM
- Longest Substring Without Repeating CharactersMEDIUM
- Max Consecutive Ones IIIMEDIUM
- Maximum Average Subarray IEASY
- Maximum Number of Vowels in a Substring of Given LengthMEDIUM
- Minimum Size Subarray SumMEDIUM
- Minimum Window SubstringHARD
- Permutation in StringMEDIUM
- Sliding Window MaximumHARD
- Substring with Concatenation of All WordsHARD