Find All Anagrams
Medium · Arrays & Hashing · Hash Table · String · Sliding Window
Problem
Given two strings s and p, return every start index i in s where the substring s[i : i + len(p)] is an anagram of p: it uses exactly the same letters with the same counts, in any order.
The indices may be returned in any order.
Examples
Input: s = "baxab", p = "ab" Output: [0,3]
The windows at 0 ("ba") and 3 ("ab") are rearrangements of "ab".
Input: s = "aaa", p = "aa" Output: [0,1]
Both overlapping windows are "aa".
Input: s = "cbaebabacd", p = "abc" Output: [0,6]
"cba" starts at 0 and "bac" at 6.
Constraints
- 1 <= s.length, p.length <= 3 * 10^4
- s and p consist of lowercase English letters
Approaches
- Baseline: sort every window — time O(|s| · |p| log |p|), space O(|p|)
Follow-up
The window here has a fixed size and must match exactly. The use cases loosen both rules: wildcards in s turn "equal counts" into "no count too high", and a window that may grow and shrink finds the longest stretch spelled from the letters of p.
Related problems
Start free on Cariara · Coding problems · System design studio
