Skip to main content

14. Find All Anagrams in a String

mediumAsked at Rappi

Return the start indices of all anagrams of p in s — Rappi frames this as scanning a stream of dispatch log lines for any permutation of a known fraud-signature substring.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Given two strings s and p, return all start indices of p's anagrams in s. The strings consist of lowercase English letters only.

Constraints

  • 1 <= s.length, p.length <= 3 * 10^4

Examples

Example 1

Input
s = "cbaebabacd", p = "abc"
Output
[0,6]

Example 2

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

Approaches

1. Sort every window

For every substring of length |p|, sort and compare to sorted p.

Time
O(n * k log k)
Space
O(k)
const sp = [...p].sort().join('');
const out = [];
for (let i=0;i+p.length<=s.length;i++)
  if ([...s.slice(i,i+p.length)].sort().join('') === sp) out.push(i);
return out;

Tradeoff:

2. Rolling 26-char counter

Maintain a frequency vector over a sliding window of size |p|; compare to the target vector in O(26) per step.

Time
O(n)
Space
O(1)
function findAnagrams(s, p) {
  if (s.length < p.length) return [];
  const need = new Array(26).fill(0), have = new Array(26).fill(0);
  const A = 'a'.charCodeAt(0);
  for (const c of p) need[c.charCodeAt(0)-A]++;
  const out = [];
  for (let i = 0; i < s.length; i++) {
    have[s.charCodeAt(i)-A]++;
    if (i >= p.length) have[s.charCodeAt(i-p.length)-A]--;
    if (need.every((v,j)=>v===have[j])) out.push(i-p.length+1);
  }
  return out;
}

Tradeoff:

Rappi-specific tips

Rappi expects fixed-size counters not hash maps — their fraud-pattern scanner runs on hot path and cannot afford per-window allocation.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill Find All Anagrams in a String and other Rappi interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →