Fixed Window + Frequency Match
Use a fixed-size window and compare character counts instead of comparing whole strings.
0 of 3 problems solved
Fixed Window + Frequency Match
Use a fixed-size window and compare character counts instead of comparing whole strings.
- •Is the window size fixed by s1.length?
- •Does order matter, or only frequency?
- •Can I compare counts instead of substrings?
Permutation in String is a fixed-size sliding window problem wearing a disguise. If s1 has length 2, then any matching permutation inside s2 must also have length 2. So you slide a window of exactly that size across s2 and compare character counts. You are not checking order. You are checking whether the same letters are present in the right amounts. Think 'bag of letters', not 'exact word'.
When order does not matter, compare frequencies, not characters one by one.
- 1Build a frequency count for s1.
- 2Slide a fixed-size window of length s1.length across s2.
- 3Update the window counts as one character enters and one leaves.
- 4If the window counts match the target counts, you found a permutation.
Comparing sorted substrings each time works, but it turns a nice sliding-window problem into unnecessary extra work.
Ransom Note
Count character frequencies in the magazine first. Then verify the ransom note never needs more of any character than the magazine provides.
Smallest Range Covering Elements from K Lists
Merge all (value, list-index) pairs into a sorted sequence. Slide a window that always covers at least one element from every list and track the minimum range width.