VietMX Staff asked 3 years ago
Problem
Example:
((()())(())) should be accepted but ())() should be rejected.
Initialize a counter at zero. Whenever you see (, increase it by one, and whenever you see ), decrease it by one. Accept if the counter was always nonnegative and ended up at zero. Since counter is always between −1 and n, only O(log n) bits (note it is not O(1)) are needed to store it. So I don’t think we can do O(1) space.
