Scrambled Pattern Windows

MediumTries & Strings

Problem

A spam filter looks for scrambled copies of a banned word. Given text and pattern, return every start index i such that text[i .. i + |pattern| - 1] is a rearrangement of pattern, in increasing order.

Example 1

Input:
text = "tacocat", pattern = "cat"
Output:
[0, 4]

"tac" at 0 and "cat" at 4 use the letters c, a, t once each.

Example 2

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

Example 3

Input:
text = "xyz", pattern = "xyzz"
Output:
[]

Constraints

  • 1 ≤ text.length, pattern.length ≤ 10^5
  • Lowercase English letters only.

Hint

Show the first hint

Consecutive windows of the same length differ by one character in and one out.

Walkthrough

How to approach it

01Clarify before coding

  • Can matches overlap? Yes, every qualifying start index is reported.
  • What if the pattern is longer than the text? Return [].
  • Only lowercase letters? Yes, 26 counters suffice.

02Brute force

For each start index, count the letters of the window from scratch and compare with the pattern.

Cost: O(n·m): 10^10 steps when both are 10^5 long.

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.