A rearrangement inside a string

mediumSliding windowHash maps and sets target 25 min

A rearrangement inside a string

Not solved yetLeetCode 567. Permutation in String

You get two strings of lowercase letters, pattern and text. A rearrangement of pattern uses exactly the same letters, each the same number of times, in any order: "eat", "tae" and "tea" itself are all rearrangements of "tea".

Return True if some block of len(pattern) consecutive letters in text is a rearrangement of pattern. Otherwise return False. If pattern is longer than text, no block fits, so the answer is False.

Example 1

Inputpattern = "tea", text = "seat"OutputTrue

The block "eat" has one e, one a and one t, the same letters as "tea".

Example 2

Inputpattern = "tea", text = "taxes"OutputFalse

The text has a t, an a and an e, but the blocks of 3 are "tax", "axe" and "xes", and each one misses at least one of them.

Example 3

Inputpattern = "aab", text = "abbab"OutputFalse

Counts matter, not only which letters appear: every block of 3 holds only one a.

Constraints

1 ≤ len(pattern) ≤ 10⁵
1 ≤ len(text) ≤ 10⁵
Both strings hold only lowercase letters a to z.

Plan it first

Write a line for each before you code, then say them out loud. Compare with the Approach tab afterwards.

Walk In what order will you visit the input?Notebook What will you write down as you go?Promise What stays true after every step?Cost Time and space, in Big O.

Run examples checks the examples. Submit runs every test, including edge cases and, when the problem has one, a speed check on a large input.

Same pattern