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

Count target frequencies in p. Use two pointers as a sliding window. Maintain a match count. When match equals map size, record left index.

function solution(s, p) {
  var need = {}, match = 0, result = [];
  for (var i = 0; i < p.length; i++) need[p[i]] = (need[p[i]] || 0) + 1;
  var left = 0, right = 0;
  while (right < s.length) {
    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);
    right++;
  }
  return result;
}

Time O(n), Space O(1).

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

Brick Wall

Word Pattern

Encode and Decode TinyURL

Duplicate Indices Map

Contains Duplicate

Valid Anagram

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.