Longest Valid Parentheses

Hard · rating 2000 · Dynamic Programming, Stack, Strings

Read a string of ( and ). Print the length of the longest contiguous substring that is a well-formed parentheses sequence.

For )()()) the answer is 4.

Constraints: 1 ≤ length ≤ 105

Editorial

Approach

Use a stack of indices seeded with a -1 sentinel that marks the boundary just before a valid run. Push every (. On a ), pop; if the stack still has an index, the distance from it to the current position is a valid length; if the stack is now empty, push the current index as a new boundary.

The sentinel trick

Keeping the index just before the last unmatched ) on the stack lets each match compute its full span in O(1).

st = [-1]; best = 0
for i, ch in enumerate(s):
    if ch == '(': st.append(i)
    else:
        st.pop()
        if st: best = max(best, i - st[-1])
        else: st.append(i)

Complexity

Time: O(n). Space: O(n).

Related problems

Open Longest Valid Parentheses in Code Arena →