Hidden Anagram Window
MediumSliding Window
Problem
A word-game checker receives a short lowercase pattern and a longer lowercase text. It must decide whether some block of pattern.length consecutive letters in text uses exactly the same letters as `pattern`, in any order.
Return true if such a block exists, otherwise false.
Example 1
- Input:
- pattern = "abc", text = "xxbcaxx"
- Output:
- true
The block "bca" is a rearrangement of "abc".
Example 2
- Input:
- pattern = "aab", text = "abbab"
- Output:
- false
The blocks "abb", "bba", "bab" each have two b's.
Constraints
- 1 ≤ pattern.length, text.length ≤ 10^5
- Both strings contain only lowercase English letters.
Hint
Show the first hint
Two strings are anagrams exactly when their letter counts match.
Walkthrough
How to approach it
01Clarify before coding
- Must the block be contiguous? Yes.
- What if pattern is longer than text? Return false.
- Do repeated letters matter? Yes, counts must match exactly.
02Brute force
For each block of length m in text, sort it and compare with sorted pattern.
Cost: O(n·m log m) time; with both near 10^5 that is hopeless.
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.
This problem is part of Pro.