Find All Anagrams in a String

Published at23 Jul 2026

Like0

Given two strings s and p, find all start indices in s where a substring is an anagram of p. Return the indices in any order. An anagram is a rearrangement of characters with the same frequency.

A sliding window approach with a hash map solves this in O(n) time. Count character frequencies in p. Slide a window of length p over s, updating frequencies. When the window frequencies match p's frequencies, record the start index. The window slides by removing the leftmost character and adding the next character to the right.

This is a classic medium problem combining hash tables with the sliding window technique.

The sliding window approach maintains a dynamic window that expands and contracts. The match counter tracks how many characters in the current window satisfy the frequency requirement. When match = len(p), all characters match and the left pointer is recorded. This avoids comparing the entire frequency map at every position.

The sliding window approach runs in O(n) time where n is the length of s. The match counter is the key optimization: instead of comparing the entire frequency map at each position, we track how many characters currently satisfy the frequency requirement. This reduces each position check to O(1).

Example Input & Output

Example 1

Input

"cbaebabacd", "abc"

Output

[0,6]

Explanation

Anagrams at index 0 (cba) and 6 (bac).

Example 2

Input

"a", "b"

Output

[]

Explanation

No anagrams found.

Example 3

Input

"abab", "ab"

Output

[0,1,2]

Explanation

Anagrams at 0 (ab), 1 (ba), 2 (ab).

Algorithm Flow

Recommendation Algorithm Flow for Find All Anagrams in a String

Solution Approach

Find all start indices in string s where a substring of length equal to string p is an anagram of p. Use a sliding window with a character frequency counter. Build a frequency map of p, then slide through s maintaining a window of the same length. At each position, compare the window's frequency map with p's map. If they match, record the start index.

function findAnagrams(s, p) {
  var need = {}, have = {}, result = [], matchCount = 0;
  for (var i = 0; i < p.length; i++) need[p[i]] = (need[p[i]] || 0) + 1;
  var uniqueChars = Object.keys(need).length;
  for (var i = 0; i < s.length; i++) {
    var c = s[i];
    have[c] = (have[c] || 0) + 1;
    if (have[c] === need[c]) matchCount++;
    if (i >= p.length) {
      var old = s[i - p.length];
      if (have[old] === need[old]) matchCount--;
      have[old]--;
      if (have[old] === 0) delete have[old];
    }
    if (matchCount === uniqueChars) result.push(i - p.length + 1);
  }
  return result;
}

Track how many character types have matching frequencies between the window and p. When matchCount equals the number of unique characters in p, the window is a valid anagram. The sliding window avoids recomputing frequencies from scratch for each position.

Time complexity is O(n), space complexity is O(k) where k is the alphabet size.

Best Answers
These are the verified best solutions for this Challenge. You can use them as a reference to improve your solution.

java

import java.util.*;
class Solution {
    public List<Integer> solution(String s, String p) {
        List<Integer> result = new ArrayList<>();
        int[] need = new int[26];
        for (char ch : p.toCharArray()) need[ch-'a']++;
        int left = 0, match = 0;
        for (int right = 0; right < s.length(); right++) {
            int idx = s.charAt(right) - 'a';
            if (--need[idx] >= 0) match++;
            if (right - left + 1 > p.length()) {
                int lidx = s.charAt(left) - 'a';
                if (++need[lidx] > 0) match--;
                left++;
            }
            if (match == p.length()) result.add(left);
        }
        return result;
    }
}

javascript

function solution(s, p) {
  var need = {}, match = 0, result = [], left = 0;
  for (var i = 0; i < p.length; i++) need[p[i]] = (need[p[i]] || 0) + 1;
  for (var right = 0; right < s.length; right++) {
    if (need[s[right]] !== undefined) { need[s[right]]--; if (need[s[right]] >= 0) match++; }
    if (right - left + 1 > p.length) {
      if (need[s[left]] !== undefined) { if (need[s[left]] >= 0) match--; need[s[left]]++; }
      left++;
    }
    if (match === p.length) result.push(left);
  }
  return result;
}

php

<?php
function solution($s, $p) {
    $need = []; $match = 0; $result = []; $left = 0;
    for ($i = 0; $i < strlen($p); $i++) $need[$p[$i]] = ($need[$p[$i]] ?? 0) + 1;
    for ($right = 0; $right < strlen($s); $right++) {
        if (isset($need[$s[$right]])) { $need[$s[$right]]--; if ($need[$s[$right]] >= 0) $match++; }
        if ($right - $left + 1 > strlen($p)) {
            if (isset($need[$s[$left]])) { if ($need[$s[$left]] >= 0) $match--; $need[$s[$left]]++; }
            $left++;
        }
        if ($match == strlen($p)) $result[] = $left;
    }
    return $result;
}

python

def solution(s, p):
    need = {}
    for ch in p: need[ch] = need.get(ch, 0) + 1
    match, result = 0, []
    left = 0
    for right, ch in enumerate(s):
        if ch in need:
            need[ch] -= 1
            if need[ch] >= 0: match += 1
        if right - left + 1 > len(p):
            if s[left] in need:
                if need[s[left]] >= 0: match -= 1
                need[s[left]] += 1
            left += 1
        if match == len(p):
            result.append(left)
    return result

rust

fn solution(s: &str, p: &str) -> Vec<i32> {
    let mut need = [0; 26];
    let mut result = vec![];
    for ch in p.chars() { need[(ch as usize)-97] += 1; }
    let (mut left, mut match_cnt) = (0, 0);
    let chars: Vec<char> = s.chars().collect();
    for right in 0..chars.len() {
        let idx = (chars[right] as usize) - 97;
        need[idx] -= 1;
        if need[idx] >= 0 { match_cnt += 1; }
        if right - left + 1 > p.len() {
            let lidx = (chars[left] as usize) - 97;
            need[lidx] += 1;
            if need[lidx] > 0 { match_cnt -= 1; }
            left += 1;
        }
        if match_cnt == p.len() as i32 { result.push(left as i32); }
    }
    result
}

typescript

function solution(s: string, p: string): number[] {
    var need: any = {}, match = 0, result: number[] = [], left = 0;
    for (var i = 0; i < p.length; i++) need[p[i]] = (need[p[i]] || 0) + 1;
    for (var right = 0; right < s.length; right++) {
        if (need[s[right]] !== undefined) { need[s[right]]--; if (need[s[right]] >= 0) match++; }
        if (right - left + 1 > p.length) {
            if (need[s[left]] !== undefined) { if (need[s[left]] >= 0) match--; need[s[left]]++; }
            left++;
        }
        if (match === p.length) result.push(left);
    }
    return result;
}

Related Hash Table Challenges

Comments (0)

Join the Discussion

Share your thoughts, ask questions, or help others with this Challenge.

Find All Anagrams in a String

Example Input & Output

Algorithm Flow

Solution Approach

Best AnswersThese are the verified best solutions for this Challenge. You can use them as a reference to improve your solution.

Solutions Coming Soon

Related Hash Table Challenges

Intersection of Two Arrays II

Number of Boomerangs

Counting Elements

Brick Wall

Design HashMap

Word Pattern

Comments (0)

Join the Discussion

Best Answers
These are the verified best solutions for this Challenge. You can use them as a reference to improve your solution.