Leetcode 32: Longest Valid Parentheses

Note the following test case “()(()” will trip up a simple counting algorithm, which was my first attempt. So I then used a stack to keep track of outstanding open bracket positions. When they are matched with a close bracket, we can mark them off in a boolean vector. We then count the longest consecutive sequence of “true”s in the bool vector. There is an alternative nice O(n) time O(1) space approach that uses the simple counting algorithm both from left to right and right to left.

This entry was posted in programming and tagged , , . Bookmark the permalink.

Leave a Reply

Your email address will not be published.