Skip to main content

19. Find All Anagrams in a String

mediumAsked at LINE

Return all start indices of substrings in s that are anagrams of p — LINE uses this to verify your sliding-window character-count instincts before chat-search problems.

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

Problem

Given two strings s and p, return an array of all the start indices of p's anagrams in s. An anagram is a rearrangement of all the characters of p, using each exactly once.

Constraints

  • 1 <= s.length, p.length <= 3 * 10^4
  • s and p consist of lowercase English letters.

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 each window

For every length-p window in s, sort and compare to sorted p.

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

Tradeoff:

2. Sliding window with char counts

Maintain a 26-slot count for p and a rolling count for the current window. Slide the window one character at a time, adjusting counts in O(1), and record indices where counts match.

Time
O(n)
Space
O(1)
function findAnagrams(s, p) {
  const out = [], pc = new Array(26).fill(0), wc = new Array(26).fill(0);
  if (p.length > s.length) return out;
  for (let i = 0; i < p.length; i++) {
    pc[p.charCodeAt(i) - 97]++;
    wc[s.charCodeAt(i) - 97]++;
  }
  const eq = () => pc.every((v, i) => v === wc[i]);
  if (eq()) out.push(0);
  for (let i = p.length; i < s.length; i++) {
    wc[s.charCodeAt(i) - 97]++;
    wc[s.charCodeAt(i - p.length) - 97]--;
    if (eq()) out.push(i - p.length + 1);
  }
  return out;
}

Tradeoff:

LINE-specific tips

At LINE, link the rolling character-count to scanning a chat-history stream for anagram-matching keyword variants — concrete chat-search framing wins.

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 LINE interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →