[Algorithm] Longest Valid Parentheses

Longest Valid Parentheses

Problem Statement:

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

For "(()", the longest valid parentheses substring is "()", which has length = 2.

Another example is ")()())", where the longest valid parentheses substring is "()()", which has length = 4.

Solution: Dynamic Programming

This problem can be solved with DP. We will have 1D array as our bookkeeping for the maximum length of valid parentheses so far.

We keep the maximum length of valid parentheses ending with ")" at ")".  If the character right before this ")" is a "(" we let dp[i] = dp[i-1] + 2. If the character right before this ")" is a "(" we need to trace back dp[i-1] number of characters (let prev = i - dp[i-1] - 1) to see if it is a unmatched "(" so we let dp[i] = (i - prev + 1) + dp[prev]

To keep this equation valid, for "(", we keep either 1) the previous sequence length prior to this "(" if there's a ")" right before it or 2) 0 if there's a ")" right before it. This is important because we need to stitch two valid sequences together to make a longer valid sequence if there's a ")(" sequence encountered.

To better explain why we are keeping the length this way let's consider these cases:


Case 1: "()()"

Our DP algorithm will have:

1 2 3

char: | ( | ) | ( | ) | index: | 0 | 1 | 2 | 3 | subLen: | 0 | 2 | 2 | 4 |

The two valid subsequences will be stitched together by dp[i] = dp[i-1] + 2, since we keep the previous subsequence length at "(" if there's a ")" right before that "(".


Case 2: "()((()))"

We have:

1 2 3

char: | ( | ) | ( | ( | ( | ) | ) | ) | index: | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | subLen: | 0 | 2 | 2 | 0 | 0 | 2 | 4 | 8 |

When we are looking at the 7th character ")", we notice this time we have a ")" at index 6, so we need to trace back to character at index 2 (7 - dp[6] - 1 = 7 - 4 - 1 = 2). We have a "(" at index 2 which is unmatched and can be matched with ")" at index 7, so dp[7] = 7 - 2 + 1 + dp[2] = 8.

Case 3: "())((()))"

We have:

1 2 3

char: | ( | ) | ) | ( | ( | ( | ) | ) | ) | index: | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | subLen: | 0 | 2 | 0 | 0 | 0 | 0 | 2 | 4 | 6 |

The ")" at index 2 does not match any open "(" so dp[2] = 0. "(" at index 3 will have the previous sequence length which is dp[3] = dp[2] = 0. So when we traceback to index 3 and we make dp[8] = 8 - 3 + 1 = 6.

Code implementation:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31

class Solution { public: int longestValidParentheses(string s) { vector<int> board(s.size(), 0); int maxLen = 0; for (int i=1; i<s.size(); i++) { if (s[i] == '(' && s[i-1] == ')') { // case 1, "()()" board[i] = board[i-1]; } if (s[i] == ')') { if (s[i-1] == ')') { // case 2, "((()))" int prev = i - board[i-1] - 1; if (prev >= 0 && s[prev] == '(') { board[i] = (i - prev + 1) + board[prev]; } } else { // case 2, inner "()" only board[i] = board[i-1] + 2; } maxLen = max(maxLen, board[i]); } } return maxLen; } };