The best algorithm I can think of takes amortized constant time and linear (proportional to window size) space. Anyone able to think of a better one? Wall Street wants you. ;-)
It's easy to prove that linear space is optimal -- you can't store N bits of information using less than N bits of space.
It's easy to prove that linear space is optimal -- you can't store N bits of information using less than N bits of space.