Anagram Window Starts

MediumSliding Window

Problem

A plagiarism tool looks for scrambled copies of a short lowercase phrase pattern inside a lowercase document text.

Return, in increasing order, every index i such that text[i .. i + pattern.length - 1] is a rearrangement of pattern. Return an empty list if there are none.

Example 1

Input:
text = "bacxcabb", pattern = "abc"
Output:
[0, 4]

The windows starting at 0 ("bac") and 4 ("cab") use exactly a, b and c.

Example 2

Input:
text = "aaaa", pattern = "aa"
Output:
[0, 1, 2]

Overlapping windows each count.

Constraints

  • 1 ≤ text.length, pattern.length ≤ 10^5
  • Both strings contain only lowercase English letters.

Hint

Show the first hint

Every window you check has the same length, len(pattern).

Walkthrough

How to approach it

01Clarify before coding

  • Return order? Increasing start index.
  • Do overlapping matches count? Yes, each start index is separate.
  • Pattern longer than text? Return an empty list.

02Brute force

For each start, count the letters of the window and compare with the pattern's counts.

Cost: O(n·m) time; with both near 10^5 that is up to 10^10 operations.

The rest of the walkthrough is in the app

The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.

Solve it in the browserStart free

This problem is part of Pro.