Find the longest run holding at most 2 distinct values. The window grows to the right, a map counts what is inside, and the window shrinks from the left whenever the map has more than 2 keys.
Finding the longest window with at most 2 distinct values, using a frequency map.
Grow right to index 0. 1 enters, a new key, so the map now has 1 distinct. Within 2, so the window is valid.
The right end moves to index 0 and 1 enters. 1 distinct values inside. That is allowed.
Grow right to index 1. 2 enters, a new key, so the map now has 2 distinct. Within 2, so the window is valid.
The right end moves to index 1 and 2 enters. 2 distinct values inside. That is allowed.
Grow right to index 2. 1 enters, its count goes to 2. Within 2, so the window is valid.
The right end moves to index 2 and 1 enters. 2 distinct values inside. That is allowed.
Grow right to index 3. 2 enters, its count goes to 2. Within 2, so the window is valid.
The right end moves to index 3 and 2 enters. 2 distinct values inside. That is allowed.
Grow right to index 4. 3 enters, a new key, so the map now has 3 distinct. That is more than 2, so the left end must shrink.
The right end moves to index 4 and 3 enters. 3 distinct values inside. Too many, so the window shrinks.
Drop 1 from the left. Its count drops to 1, still inside, so the map keeps 3 keys. Still over 2, shrink again.
The left end moves to index 1, dropping 1. 3 distinct values remain. Still too many.
Drop 2 from the left. Its count drops to 1, still inside, so the map keeps 3 keys. Still over 2, shrink again.
The left end moves to index 2, dropping 2. 3 distinct values remain. Still too many.
Drop 1 from the left. Its count hits zero, so it leaves the map: 2 distinct now. Back within 2.
The left end moves to index 3, dropping 1. 2 distinct values remain.
Grow right to index 5. 3 enters, its count goes to 2. Within 2, so the window is valid.
The right end moves to index 5 and 3 enters. 2 distinct values inside. That is allowed.
Grow right to index 6. 4 enters, a new key, so the map now has 3 distinct. That is more than 2, so the left end must shrink.
The right end moves to index 6 and 4 enters. 3 distinct values inside. Too many, so the window shrinks.
Drop 2 from the left. Its count hits zero, so it leaves the map: 2 distinct now. Back within 2.
The left end moves to index 4, dropping 2. 2 distinct values remain.
Grow right to index 7. 2 enters, a new key, so the map now has 3 distinct. That is more than 2, so the left end must shrink.
The right end moves to index 7 and 2 enters. 3 distinct values inside. Too many, so the window shrinks.
Drop 3 from the left. Its count drops to 1, still inside, so the map keeps 3 keys. Still over 2, shrink again.
The left end moves to index 5, dropping 3. 3 distinct values remain. Still too many.
Drop 3 from the left. Its count hits zero, so it leaves the map: 2 distinct now. Back within 2.
The left end moves to index 6, dropping 3. 2 distinct values remain.
Grow right to index 8. 2 enters, its count goes to 2. Within 2, so the window is valid.
The right end moves to index 8 and 2 enters. 2 distinct values inside. That is allowed.
The longest window with at most 2 distinct values is indices 0 to 3, length 4. Each end moved forward only, 15 moves in all, so O(n), and the map answered every distinct-count question in O(1).
The longest window with at most 2 distinct values has length 4, from index 0 to 3.