Find All Anagrams in a String
Problem statement
You're given two strings, s and p. Find every starting position in s where the characters from that position onward, for the length of p, use exactly the same letters as p — the same multiset of characters, in any order (an anagram). Return all those starting positions.
Think of p as a fixed "signature" of tokens you're watching for — say, a set of five distinct status codes — and s as a longer log of tokens. This finds every window in the log that contains exactly that signature, in any order, which is a building block for detecting a known event pattern appearing somewhere in a stream, regardless of the order its parts arrive in.
Examples
Example 1
Input: s = "cbaebabacd", p = "abc"
Output: [0, 6]
Explanation: The window starting at index 0 is "cba", which uses the same letters as "abc". The window starting at index 6 is "bac", also the same letters. No other window of length 3 matches.
Example 2
Input: s = "abab", p = "ab"
Output: [0, 1, 2]
Explanation: Every window of length 2 in "abab" — "ab", "ba", "ab" — uses exactly the letters a and b, so all three starting positions qualify.
Hints
p works, but sorting each window costs extra time you don't need to spend.Approach
Optimal: Sliding window with a running count
Intuition
The better approach still rebuilds the window's entire count array from scratch at every position, even though sliding the window by one only changes two characters: the one that just left on the left, and the one that just entered on the right. So instead of rebuilding, keep one running count array and update it incrementally — increment the count for the character entering, and decrement the count for the character leaving once the window is full-sized. That reduces each slide to two O(1) array updates instead of an O(m) rebuild.
Steps
- Build a 26-entry count array
targetCountfromp. - Keep a 26-entry count array
windowCount, starting empty. - Loop
ifrom0tolen(s) - 1:- Increment
windowCountfors[i](the character entering the window). - If the window is now larger than
len(p), decrementwindowCountfor the character that just fell off the left (s[i - len(p)]). - Once the window has reached exactly
len(p)characters (i >= len(p) - 1), comparewindowCounttotargetCount; if equal, record the window's starting index (i - len(p) + 1).
- Increment
- Return the list of recorded starting indices.
Dry run
s = "abab", p = "ab" → targetCount = {a:1, b:1}
| i | s[i] | windowCount after add | window full & drop? | windowCount after drop | matches target? | recorded start |
|---|---|---|---|---|---|---|
| 0 | a | {a:1} | not yet (i < 1) | {a:1} | not checked (i < 1) | — |
| 1 | b | {a:1, b:1} | i ≥ 2? no | {a:1, b:1} | yes | 0 |
| 2 | a | {a:2, b:1} | i ≥ 2 → drop s[0]='a' | {a:1, b:1} | yes | 1 |
| 3 | b | {a:1, b:2} | i ≥ 2 → drop s[1]='b' | {a:1, b:1} | yes | 2 |
All three starts match, giving [0, 1, 2], matching the example.
Edge cases: if p is longer than s, the function returns immediately with an empty list before the loop even starts, avoiding any out-of-range access; the window only starts being compared once it has actually reached len(p) characters (i >= m - 1), so a partially-filled window is never mistakenly checked.
Complexity
Time O(n + m) - building the target count from `p` takes O(m), and the window then slides across `s` once, doing O(1) work per character by updating the running count instead of rebuilding it.
Space O(1) - two fixed-size, 26-entry count arrays, no matter how large `s` or `p` are.
class Solution:
def findAnagrams(self, s: str, p: str) -> list[int]:
n, m = len(s), len(p)
if m > n:
return []
target_count = [0] * 26
window_count = [0] * 26
def idx(c):
return ord(c) - ord('a')
for c in p:
target_count[idx(c)] += 1
result = []
for i in range(n):
window_count[idx(s[i])] += 1
if i >= m:
window_count[idx(s[i - m])] -= 1
if i >= m - 1 and window_count == target_count:
result.append(i - m + 1)
return result
if __name__ == "__main__":
print(Solution().findAnagrams("cbaebabacd", "abc")) # [0, 6]
print(Solution().findAnagrams("abab", "ab")) # [0, 1, 2]RecapThe whole problem in a few lines, for the night before
- Spot it: every start index in s where a substring is an anagram of p
- Idea: slide a window of length len(p) and keep letter counts; compare the window counts with p's counts as you move one step at a time
- Cost: O(n) time, O(1) space (26 letters)
- Trap: update the counts incrementally; rebuilding the count for every window makes it slow
Interview follow-ups
What if
sorpcould contain uppercase letters, digits, or Unicode characters, not just lowercase English letters?The fixed 26-entry array assumption breaks, so the count structure needs to grow: a hash map keyed by character (or, for a bounded but larger alphabet like ASCII, a 256-entry array) instead of a 26-entry array. The sliding-window logic itself — add on entry, remove on exit, compare when the window is full — stays exactly the same; only the size and type of the count structure changes.
What if you needed to find anagrams of
pin a live stream ofswhere you can't store the whole string?The sliding-window approach already only needs to remember the last
len(p)characters and a running count, not the whole string, so it adapts naturally: keep a small circular buffer (or just track which character indexi - len(p)refers to as it streams in) alongside the running count array, and emit a match the moment a full window's counts align — the memory footprint stays O(1) relative to how much of the stream has passed.
Frequently asked questions
An anagram is defined purely by "uses exactly the same letters, the same number of times each" — order doesn't matter at all. Two strings with identical character counts are, by definition, rearrangements of each other, so comparing counts is both necessary and sufficient; sorting is just a slower way of arriving at the same conclusion.
Finding every place in a longer sequence where a fixed-size window matches a known "signature" — regardless of the order its parts appear in — comes up when scanning a log or event stream for a known pattern of tokens (say, a specific set of five status codes appearing together within a short window, in any order). It's also a common way to test whether a candidate can spot that a fixed-size sliding window with incremental updates beats rebuilding a full comparison at every position.
Since the problem guarantees only lowercase English letters, a 26-entry array gives O(1) true constant-time access and comparison, with no hashing overhead and no risk of an unbounded number of distinct keys. A hash map would still work correctly, but the array is simpler and faster here specifically because the alphabet is small and fixed.
They're the same underlying check — "do these two equal-length strings have the same character counts" — but this problem asks for every matching starting position across the whole of s, not just a single yes/no answer for one particular substring. That's exactly why a sliding window that checks every position efficiently, rather than one isolated comparison, is the right tool here.
