Find All Anagrams in a String

Medium
33.

Find All Anagrams in a String

Find All Anagrams in a String is a medium coding problem on strings, hash table and sliding window, asked in Databricks interviews.

Given two strings s and p, return an array of all the start indices of p's anagrams in s, in increasing order.

Example 1

Input
s = "cbaebabacd", p = "abc"
Output
[0,6]
Explanation
Substrings "cba" (index 0) and "bac" (index 6).

Example 2

Input
s = "abab", p = "ab"
Output
[0,1,2]

Constraints

  • 1 <= s.length, p.length <= 40
  • s and p consist of lowercase English letters.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @param {string} p
 * @return {number[]}
 */
var findAnagrams = function(s, p) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Find All Anagrams in a String — Problem & Solution

Find All Anagrams in a String solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Find All Anagrams in a String is a medium coding problem on strings, hash table and sliding window, asked in Databricks interviews.

  • Difficulty: Medium
  • Topics: Strings, Hash Table, Sliding Window
  • Asked at: Databricks
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Given two strings s and p, return an array of all the start indices of p's anagrams in s, in increasing order.

Example 1

Input: s = "cbaebabacd", p = "abc"
Output: [0,6]
Explanation: Substrings "cba" (index 0) and "bac" (index 6).

Example 2

Input: s = "abab", p = "ab"
Output: [0,1,2]

Constraints

  • 1 <= s.length, p.length <= 40
  • s and p consist of lowercase English letters.

Hints for Find All Anagrams in a String

  1. Hint 1

    Compare letter-frequency counts of a sliding window of length |p| against p's counts.

  2. Hint 2

    Update the window counts incrementally: add the entering char, remove the leaving one.

How to solve Find All Anagrams in a String

An anagram of p is any window of s with the same length and the same character frequencies. So slide a fixed-width window of size |p| across s, updating counts incrementally, and record every position where the tables agree.

Approach

  1. Build a frequency table for p.
  2. Slide a window of width |p| across s, adding the entering character's count.
  3. Once the window is wider than |p|, subtract the character leaving on the left.
  4. When the window reaches full width, compare the two tables and record the start index on a match.
  5. Return the indices in the order found, which is already increasing.

Why it works

Two equal-length strings are anagrams exactly when their character multisets match, and a fixed-size count table is that multiset. Updating incrementally — one addition and one removal per step — is what keeps the sweep linear instead of rebuilding a table for every window. Because the window advances left to right, the recorded indices come out sorted with no extra work.

Complexity

  • Time — O(|s| · alphabet)
  • Space — O(1)

Pitfalls

  • The window is fixed width; growing and shrinking it solves a different problem.
  • Remove the outgoing character as well as adding the incoming one.
  • Start recording only once the window is exactly |p| wide.
  • If p is longer than s the answer is empty, which falls out because the window never fills.

Reference solution

Python

from typing import List

def findAnagrams(s: str, p: str) -> List[int]:
    out = []
    if len(p) > len(s):
        return out
    need = [0] * 26
    have = [0] * 26
    for ch in p:
        need[ord(ch) - 97] += 1
    for i, ch in enumerate(s):
        have[ord(ch) - 97] += 1
        if i >= len(p):
            have[ord(s[i - len(p)]) - 97] -= 1
        if i >= len(p) - 1 and have == need:
            out.append(i - len(p) + 1)
    return out

Java

public static int[] findAnagrams(String s, String p) {
    List<Integer> out = new ArrayList<>();
    int n = s.length(), m = p.length();
    if (m <= n) {
        int[] need = new int[26];
        int[] have = new int[26];
        for (int i = 0; i < m; i++) need[p.charAt(i) - 'a']++;
        for (int i = 0; i < n; i++) {
            have[s.charAt(i) - 'a']++;
            if (i >= m) have[s.charAt(i - m) - 'a']--;
            if (i >= m - 1 && Arrays.equals(need, have)) out.add(i - m + 1);
        }
    }
    int[] res = new int[out.size()];
    for (int i = 0; i < out.size(); i++) res[i] = out.get(i);
    return res;
}

C++

vector<int> findAnagrams(string s, string p) {
    vector<int> out;
    int n = (int) s.size(), m = (int) p.size();
    if (m > n) return out;
    vector<int> need(26, 0), have(26, 0);
    for (int i = 0; i < m; i++) need[p[i] - 'a']++;
    for (int i = 0; i < n; i++) {
        have[s[i] - 'a']++;
        if (i >= m) have[s[i - m] - 'a']--;
        if (i >= m - 1 && need == have) out.push_back(i - m + 1);
    }
    return out;
}

JavaScript

var findAnagrams = function(s, p) {
    const out = [];
    if (p.length > s.length) return out;
    const need = new Array(26).fill(0);
    const have = new Array(26).fill(0);
    for (const ch of p) need[ch.charCodeAt(0) - 97]++;
    for (let i = 0; i < s.length; i++) {
        have[s.charCodeAt(i) - 97]++;
        if (i >= p.length) have[s.charCodeAt(i - p.length) - 97]--;
        if (i >= p.length - 1) {
            let ok = true;
            for (let j = 0; j < 26; j++) {
                if (need[j] !== have[j]) { ok = false; break; }
            }
            if (ok) out.push(i - p.length + 1);
        }
    }
    return out;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings · Hashing: Hash Maps and Hash Sets