Sliding Window + Set
Expand the window when valid, shrink it the moment a duplicate breaks the rule.
0 of 3 problems solved
Sliding Window + Set
Expand the window when valid, shrink it the moment a duplicate breaks the rule.
- •Is the window valid only while characters are unique?
- •Do duplicates force the left pointer to move?
- •Am I tracking the longest valid window?
Sliding window sounds fancy, but it is really just a moving rectangle over your string. For this problem, the rule is simple: the window must never contain duplicate characters. So you expand to the right to grow your answer, and when a duplicate sneaks in, you shrink from the left until the rule is true again. It feels like running a tiny nightclub: if the same guest appears twice, somebody has to leave before the party continues.
Expand when the window is valid. Shrink only when the rule is broken.
- 1Use a left pointer and a right pointer to describe the current window.
- 2Keep a Set of the characters currently inside the window.
- 3Add the right character if it is new.
- 4If it is a duplicate, move the left pointer and remove characters until the duplicate is gone.
- 5Track the biggest valid window length.
Only moving the right pointer after finding a duplicate leaves the broken window unchanged. The left side has to shrink until the rule is fixed.
Contains Duplicate II
Maintain a Set as your sliding window. Before inserting a new element, remove the one that would push the window past size k.
Substring with Concatenation of All Words
Slide a window that moves one word-length at a time. Track word counts in the window with a HashMap and compare to the target count map.