Find All Anagrams — Problem Statement & Solution Guide
Quick Answer & Algorithm Key Takeaway
Master coding challenges related to Sliding Window and solve the Find All Anagrams problem optimally.
O(n)O(1)Problem Description
Given a string s and a pattern string p, identify all starting indices in s where a substring of length equal to p is an anagram of p. An anagram is defined as a permutation of characters such that the frequency of each character in the substring matches the frequency of the corresponding character in p exactly.
The input consists of two strings, s and p, composed solely of lowercase English letters. The output should be a list of integers representing the 0-based starting positions of all valid anagram substrings within s. If no such substrings exist, return an empty list. The order of indices in the output list must be ascending.
This problem requires efficient detection of character frequency matches across a sliding window of fixed size. A brute-force approach checking every substring would be computationally expensive; therefore, an optimized solution leveraging frequency counting and window shifting is expected.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Find All Anagrams"
WHY DOES IT MATTER?
The sliding window pattern is essential because it transforms a potentially quadratic problem into a linear one by reusing previously computed information. It allows the algorithm to process each character of the string exactly once, which is critical for meeting strict time constraints in production systems and coding interviews.
OPTIMIZATION CHALLENGE
The core insight is that an anagram can be detected by comparing frequency counts rather than the actual substring. By maintaining a single counter that tracks how many characters have matching frequencies, we avoid full array comparisons at each step, reducing the per-step cost to O(1).
REAL-WORLD CONNECTION
In distributed log processing, a sliding window is used to compute rolling metrics (e.g., error rates over the last N minutes). Similarly, the anagram problem slides a window over the input string to maintain a running count of character frequencies, analogous to maintaining a moving summary of log entries.
When explaining the solution, emphasize that the window size is fixed to |p|, so the algorithm never needs to resize the frequency array. Also, point out that the counter of matching characters can be incremented or decremented in constant time, which is a subtle but powerful optimization.
COMPLEXITY AT A GLANCE
O(n)O(1)Core Theory — Why This Approach?
The problem of finding all anagrammatic substrings is a classic example of the sliding window paradigm applied to string matching. A naive solution would generate every substring of length |p| from s, sort it, and compare it to the sorted pattern p, resulting in O(n·|p|·log|p|) time and O(|p|) space for each comparison. This approach quickly becomes infeasible for large inputs because the number of substrings grows linearly with n while each comparison is expensive.
The optimal solution leverages the fact that an anagram is defined solely by character frequencies. By maintaining two frequency arrays of size 26 (for lowercase English letters), one for the pattern and one for the current window in s, we can update the window in constant time as we slide it one character at a time. The key insight is that two windows are anagrams if and only if their frequency arrays are identical. We can compare the arrays in O(1) time by keeping a counter of how many characters have matching counts, updating it incrementally as the window moves. This reduces the overall time complexity to O(n) and space complexity to O(1), independent of the length of the pattern.
The sliding window technique is powerful because it transforms a problem that initially seems to require repeated expensive operations into one that requires only constant-time updates per step. It is widely used in problems involving substrings, subarrays, and contiguous segments where the property of interest can be expressed as a cumulative measure that can be incrementally maintained.
Interview Questions on This Problem
Q1What is the time complexity of the optimal solution for finding all anagram indices in a string, and why does it achieve this bound?
The optimal solution runs in O(n) time, where n is the length of the string s. It achieves this bound by using a sliding window of fixed size |p| and updating character frequency counts in constant time as the window moves one character at a time, avoiding repeated sorting or recomputation.
Q2How would you modify the algorithm if the input strings could contain Unicode characters beyond the 26 lowercase English letters?
Instead of fixed-size arrays, use a hash map (e.g., unordered_map in C++ or a dictionary in Python) to store character counts. The sliding window updates would then involve incrementing and decrementing counts in the map, and the equality check would compare the two maps, which remains O(1) on average if the alphabet size is bounded or O(k) where k is the number of distinct characters in the window.
Q3During an interview, a candidate suggests using a rolling hash to detect anagrams. Why is this approach unsuitable for this problem?
A rolling hash is designed to detect identical substrings, not anagrams, because it preserves the order of characters. Anagrams can have the same multiset of characters but different orders, so a hash that depends on order would fail to recognize them. The frequency-based sliding window is the correct approach for anagram detection.
Examples
Input
s = "abab", p = "ab"
Output
[0, 1, 2]
Explanation: The length of p is 2. We check substrings of length 2 in s: 1. Index 0: substring "ab". Frequencies: {a:1, b:1}. Matches p's frequencies {a:1, b:1}. Valid. 2. Index 1: substring "ba". Frequencies: {b:1, a:1}. Matches p's frequencies. Valid. 3. Index 2: substring "ab". Frequencies: {a:1, b:1}. Matches p's frequencies. Valid. Thus, the starting indices are 0, 1, and 2.
Input
s = "cbaebabacd", p = "abc"
Output
[0, 6]
Explanation: The length of p is 3. We check substrings of length 3 in s: 1. Index 0: "cba" -> {c:1, b:1, a:1}. Matches {a:1, b:1, c:1}. Valid. 2. Index 1: "bba" -> {b:2, a:1}. Mismatch (b count differs). 3. Index 2: "bab" -> {b:2, a:1}. Mismatch. 4. Index 3: "aba" -> {a:2, b:1}. Mismatch. 5. Index 4: "bac" -> {b:1, a:1, c:1}. Matches. Valid. Wait, let's re-verify index 4. s[4:7] is "bac"? s is c-b-a-e-b-a-b-a-c-d. Indices: 0:c, 1:b, 2:a, 3:e, 4:b, 5:a, 6:b, 7:a, 8:c, 9:d. Index 0: cba -> {c:1,b:1,a:1}. Match. Index 1: bae -> {b:1,a:1,e:1}. No match (e not in p). Index 2: aeb -> {a:1,e:1,b:1}. No match. Index 3: eba -> {e:1,b:1,a:1}. No match. Index 4: bab -> {b:2,a:1}. No match. Index 5: aba -> {a:2,b:1}. No match. Index 6: bac -> {b:1,a:1,c:1}. Match. Index 7: acd -> {a:1,c:1,d:1}. No match. So valid indices are 0 and 6.
Input
s = "a", p = "a"
Output
[0]
Explanation: The length of p is 1. The only substring of length 1 in s is "a" at index 0. Its frequency {a:1} matches p's frequency {a:1}. Thus, index 0 is the only valid starting position.
Constraints
- 1 <= s.length <= 10^4
- 1 <= p.length <= s.length
- s and p consist of lowercase English letters only.
Optimal Approach & Strategy
Use a sliding window with two 26‑element frequency arrays. Update the window in O(1) per move and compare arrays in O(1), achieving O(n) time and O(1) space.
Brute Force Approach
Generate every substring of length |p| from s, sort each substring, and compare it to the sorted pattern. This takes O(n·|p|·log|p|) time and O(|p|) space for sorting.
Code Solutions
function findAnagrams(s, p) {
const result = [];
if (s.length < p.length) return result;
const need = new Array(26).fill(0), window = new Array(26).fill(0);
for (const ch of p) need[ch.charCodeAt(0) - 97]++;
let left = 0;
for (let right = 0; right < s.length; right++) {
window[s.charCodeAt(right) - 97]++;
if (right - left + 1 > p.length) {
window[s.charCodeAt(left) - 97]--;
left++;
}
if (right - left + 1 === p.length) {
let match = true;
for (let i = 0; i < 26; i++) {
if (window[i] !== need[i]) { match = false; break; }
}
if (match) result.push(left);
}
}
return result;
}#include <vector>
#include <string>
using namespace std;
vector<int> findAnagrams(string s, string p) {
vector<int> result;
if (s.size() < p.size()) return result;
vector<int> need(26, 0), window(26, 0);
for (char c : p) need[c - 'a']++;
int left = 0;
for (int right = 0; right < (int)s.size(); ++right) {
window[s[right] - 'a']++;
if (right - left + 1 > (int)p.size()) {
window[s[left] - 'a']--;
++left;
}
if (right - left + 1 == (int)p.size() && window == need) {
result.push_back(left);
}
}
return result;
}import java.util.*;
class Solution {
public List<Integer> findAnagrams(String s, String p) {
List<Integer> result = new ArrayList<>();
if (s.length() < p.length()) return result;
int[] need = new int[26];
int[] window = new int[26];
for (char ch : p.toCharArray()) need[ch - 'a']++;
int left = 0;
for (int right = 0; right < s.length(); right++) {
window[s.charAt(right) - 'a']++;
if (right - left + 1 > p.length()) {
window[s.charAt(left) - 'a']--;
left++;
}
if (right - left + 1 == p.length() && Arrays.equals(window, need)) {
result.add(left);
}
}
return result;
}
}def find_anagrams(s: str, p: str) -> List[int]:
result = []
if len(s) < len(p):
return result
need = [0] * 26
window = [0] * 26
for ch in p:
need[ord(ch) - 97] += 1
left = 0
for right, ch in enumerate(s):
window[ord(ch) - 97] += 1
if right - left + 1 > len(p):
window[ord(s[left]) - 97] -= 1
left += 1
if right - left + 1 == len(p) and window == need:
result.append(left)
return resultfunction findAnagrams(s, p) {
const result = [];
if (s.length < p.length) return result;
const need = new Array(26).fill(0), window = new Array(26).fill(0);
for (const ch of p) need[ch.charCodeAt(0) - 97]++;
let left = 0;
for (let right = 0; right < s.length; right++) {
window[s.charCodeAt(right) - 97]++;
if (right - left + 1 > p.length) {
window[s.charCodeAt(left) - 97]--;
left++;
}
if (right - left + 1 === p.length) {
let match = true;
for (let i = 0; i < 26; i++) {
if (window[i] !== need[i]) { match = false; break; }
}
if (match) result.push(left);
}
}
return result;
}Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.