Longest run of trades with no repeated symbol

Question

You have the sequence of symbols printed on a venue, one per tick. Find the length of the longest contiguous stretch in which no symbol repeats (every symbol inside the window is distinct).

symbols = ["A", "B", "C", "A", "D", "B"]
-> 4            # the stretch C A D B is all distinct

Return the maximum window length. Aim for $O(n)$ .

Accepted Answer

Use a variable-size sliding window plus a hash map recording the last index at which each symbol appeared. Extend right one tick at a time. If the new symbol was seen at some position = left, that is a repeat inside the window, so jump left to just past that earlier occurrence. The window [left, right] is always repeat-free, and its length is a candidate for the best. Tracing the example: the window grows A B C (all distinct), then A at index 3 repeats the A at index 0, so left jumps to 1, giving B C A. Then D extends it to B C A D, and finally B at index 5 repeats the B at index 1, so left j…

Longest run of trades with no repeated symbol

Your answer

More Coding questions