32. Longest Valid Parentheses
LeetCode 32. Longest Valid Parentheses****
Description
Given a string containing just the characters '('
and ')'
, find the length of the longest valid (well-formed) parentheses substring.
Example 1:
Example 2:
Example 3:
Constraints:
0 <= s.length <= 3 * 104
s[i]
is'('
, or')'
.
Tags
String, Dynamic Programming
Solution
We make use of 2 counters l
and r
to count '('
and ')'
. We iterate through the string twice, once from left to right, and once the other way around. Whenever left becomes equal to right, we calculate the length of the current valid string and keep track of maximum length substring found so far. In the forward traversal, if right becomes greater than left we reset left and right to 0, vice versa.
Complexity
Time complexity:
Space complexity:
Code
Reference
Last updated
Was this helpful?