Find All Starting Indices of Anagrams in a String

Medium20–25 min

Topics

StringSliding WindowHash Table

Companies

AmazonMicrosoftFacebookGoogle

Given two lowercase strings s and p, return every starting index in s where a contiguous substring is an anagram (a permutation, rearranged) of p. This is the "find all" version of checking for a single permutation: instead of stopping at the first match, every window of s must be checked. A window is a match precisely when its 26-letter frequency count equals p's. Rebuilding that count for every window works, but the sliding window technique keeps the count updated in O(1) per slide — bump the letter entering, drop the letter leaving — instead of recounting all of p.length letters every time.

Test Case 1:

Input:s = "aabb", p = "ab"

Output:[1]

Explanation:Only the window "ab" at index 1 has the same letter counts as p; "aa" and "bb" don't.

Test Case 2:

Input:s = "cbaebabacd", p = "abc"

Output:[0, 6]

Explanation:"cba" at index 0 and "bac" at index 6 are both anagrams of "abc".

Test Case 3:

Input:s = "abab", p = "ab"

Output:[0, 1, 2]

Explanation:Every length-2 window of s is an anagram of p.

Constraints

◆1 ≤ s.length, p.length ≤ 3 × 10⁴
◆s and p consist of lowercase English letters only

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

🧪Try your own test case

s (lowercase) — 3-12 lowercase lettersp (lowercase) — 1-5 lowercase letters, at most as long as s

1	class Solution {
2	public int[] findAnagramStartIndices(String s, String p) {
3	int n = p.length(), m = s.length();
4	int[] temp = new int[Math.max(m, 1)];
5	int count = 0;
6	if (n > m) return new int[0];
7	int[] need = new int[26], window = new int[26];
8	for (char c : p.toCharArray()) need[c - 'a']++;
9	for (int i = 0; i < n; i++) window[s.charAt(i) - 'a']++;
10	if (Arrays.equals(need, window)) temp[count++] = 0;
11	for (int i = n; i < m; i++) {
12	window[s.charAt(i) - 'a']++;
13	window[s.charAt(i - n) - 'a']--;
14	if (Arrays.equals(need, window)) temp[count++] = i - n + 1;
15	}
16	return Arrays.copyOf(temp, count);
17	}
18	}
19

↑left

↑right

Variables

window"aa"

BUILD_WINDOW

Build p's frequency count and the very first window of s, "aa".

Step 1 / 7

Approach & Solutions

Brute Force

Brute

Build a 26-letter frequency count for p. Then for every window of length p.length in s, build that window's own frequency count from scratch and compare it against p's, recording the start index on a match. Correct, but rebuilding a fresh count for every single window throws away almost all of the work done for the window right before it.

TimeO(n · 26)

SpaceO(n)

Java

Try it out

class Solution {
    public int[] findAnagramStartIndices(String s, String p) {
        int n = p.length(), m = s.length();
        int[] temp = new int[Math.max(m, 1)];
        int count = 0;
        if (n > m) return new int[0];
        int[] need = new int[26];
        for (char c : p.toCharArray()) need[c - 'a']++;
        for (int i = 0; i <= m - n; i++) {
            int[] window = new int[26];
            for (int j = i; j < i + n; j++) window[s.charAt(j) - 'a']++;
            if (Arrays.equals(need, window)) temp[count++] = i;
        }
        return Arrays.copyOf(temp, count);
    }
}

Optimal — Sliding Window

Optimal

Build p's 26-letter frequency count once, and the very first window's frequency count once. Compare them. Then slide the window one character at a time: bump the count of the character entering on the right, drop the count of the character leaving on the left, and compare again — recording the start index whenever it matches — no need to rebuild the whole window's count from scratch on every slide.

TimeO(n)