438. Find All Anagrams in a String
mediumAsked at CiscoFind All Anagrams at Cisco is a fixed-window sliding-window problem with a frequency invariant. The interviewer is checking whether you maintain the window's char counts incrementally rather than re-counting from scratch at every position.
By Alex Chen, Founder, InterviewChamp.AI · Last verified
Source citations
Public interview reports confirming this problem appears in Cisco loops.
- Glassdoor (2026-Q1)— Cisco SDE-II interview reports cite this as a 30-minute sliding-window round.
- Blind (2025-09)— Cisco interview thread lists Find All Anagrams as a recurring sliding-window problem.
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, using all the original letters exactly once.
Constraints
1 <= s.length, p.length <= 3 * 10^4s and p consist of lowercase English letters.
Examples
Example 1
s = "cbaebabacd", p = "abc"[0,6]Explanation: Substrings starting at indices 0 ("cba") and 6 ("bac") are anagrams of "abc".
Example 2
s = "abab", p = "ab"[0,1,2]Approaches
1. Brute-force: sort each window
For each window of length p.length in s, sort it and compare to sorted p.
- Time
- O(n * k log k)
- Space
- O(k)
function findAnagramsBrute(s, p) {
const result = [];
const sortedP = [...p].sort().join('');
const k = p.length;
for (let i = 0; i + k <= s.length; i++) {
if ([...s.slice(i, i + k)].sort().join('') === sortedP) result.push(i);
}
return result;
}Tradeoff: Quadratic-ish — each sort is O(k log k) and we do n-k of them. TLEs on the LeetCode upper bound. Useful only to show you understand the semantics.
2. Sliding window with char count (optimal)
Maintain a 26-int array for the current window's char frequencies. Compare to p's frequencies. Slide by adding the new char, removing the old char, and re-checking.
- Time
- O(n)
- Space
- O(1) — 26 ints
function findAnagrams(s, p) {
const result = [];
if (s.length < p.length) return result;
const need = new Array(26).fill(0);
const have = new Array(26).fill(0);
const A = 'a'.charCodeAt(0);
for (const c of p) need[c.charCodeAt(0) - A]++;
const k = p.length;
for (let i = 0; i < s.length; i++) {
have[s.charCodeAt(i) - A]++;
if (i >= k) have[s.charCodeAt(i - k) - A]--;
if (i >= k - 1 && need.every((v, j) => v === have[j])) {
result.push(i - k + 1);
}
}
return result;
}Tradeoff: O(n) traversal; each window comparison is O(26) = O(1). The `every` per position is a 26-op cost. Cisco interviewers accept this; the absolute-optimal uses a `matches` counter (below) to drop the 26-op compare to O(1).
3. Sliding window with matches counter (absolute optimal)
Track a `matches` counter that increments when have[c] becomes equal to need[c] and decrements when it stops matching. Match found when matches === 26.
- Time
- O(n)
- Space
- O(1)
function findAnagramsMatches(s, p) {
const result = [];
if (s.length < p.length) return result;
const need = new Array(26).fill(0);
const have = new Array(26).fill(0);
const A = 'a'.charCodeAt(0);
for (const c of p) need[c.charCodeAt(0) - A]++;
let matches = 0;
for (let i = 0; i < 26; i++) if (need[i] === 0) matches++;
const k = p.length;
for (let i = 0; i < s.length; i++) {
const inIdx = s.charCodeAt(i) - A;
have[inIdx]++;
if (have[inIdx] === need[inIdx]) matches++;
else if (have[inIdx] === need[inIdx] + 1) matches--;
if (i >= k) {
const outIdx = s.charCodeAt(i - k) - A;
have[outIdx]--;
if (have[outIdx] === need[outIdx]) matches++;
else if (have[outIdx] === need[outIdx] - 1) matches--;
}
if (matches === 26) result.push(i - k + 1);
}
return result;
}Tradeoff: Drops the inner 26-loop on every position to O(1). Same Big-O on paper but the constant factor matters on the 30k upper bound. Cisco interviewers love the optimization but accept the simpler version above.
Cisco-specific tips
Cisco interviewers grade this on whether you reach for the SLIDING WINDOW pattern, not nested loops. Say it out loud: 'I maintain a frequency map of the current window — when I slide, I add one char and remove one char, both O(1). The comparison is O(26) which is constant.' If they push harder, mention the matches-counter optimization. The framing 'this is a fixed-window problem where the invariant is char frequency = p's frequency' is the entire signal.
Common mistakes
- Recounting the window from scratch on each position — turns the algorithm into O(n*k).
- Forgetting to remove the OUTGOING char when the window slides past k chars — invariant breaks immediately.
- Comparing the full count arrays via JSON.stringify or .join — works but slow; use `every` or the matches counter.
Follow-up questions
An interviewer at Cisco may pivot to one of these next:
- Permutation in String (LC 567) — same algorithm; return true/false instead of all indices.
- Minimum Window Substring (LC 76) — VARIABLE-width sliding window; harder.
- Longest Substring Without Repeating Characters (LC 3) — variable-width with a different invariant.
- What if p contains characters from a larger alphabet (Unicode)? — use a Map instead of fixed 26-array.
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
FAQ
Sliding window or hash map?
Both — sliding window is the OUTER algorithm, the frequency counter is the data structure that powers the O(1) per-step update. The interviewer wants to hear both: 'sliding window of size k, maintaining a frequency map of the window.'
Why 26-int array instead of a Map?
Because the problem guarantees lowercase English letters. A 26-int array is 4x faster than a Map (object hash overhead is the killer). Cisco interviewers reward this — and ask 'what if it were Unicode?' to test whether you'd pivot to a Map.
Free learning resources
Curated free links for this problem.
Practice these live with InterviewChamp.AI
Drill Find All Anagrams in a String and other Cisco interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.
Practice these live with InterviewChamp.AI →