Longest window where no symbol repeats thrice

Question

Given the tape as a sequence of symbols, find the length of the longest contiguous stretch in which no symbol appears more than twice.

symbols = ["A", "B", "A", "A", "B"]
-> 4            # the stretch B A A B: A twice, B twice

Return the maximum window length in which every symbol's count is at most two. Aim for $O(n)$ .

Accepted Answer

Slide a variable window with a count map. Extend the right edge one symbol at a time. The only symbol that can violate the "at most twice" rule is the one just added, so if its count hits three, shrink from the left until that specific symbol drops back to two. Because adding never fixes a violation, once invalid you must shrink, and each index enters and leaves the window once. Tracing ["A", "B", "A", "A", "B"]: at the third A the count of A hits three, so the left edge slides past the first A, leaving the window B A A B of length 4, which is the answer. Time O(n), left advances at most n ti…

Longest window where no symbol repeats thrice

Your answer

More Coding questions