LeetCode-in-All
32. Longest Valid Parentheses
Hard
Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.
Example 1:
Input: s = “(()”
Output: 2
Explanation: The longest valid parentheses substring is “()”.
Example 2:
Input: s = “)()())”
Output: 4
Explanation: The longest valid parentheses substring is “()()”.
Example 3:
Input: s = “”
Output: 0
Constraints:
0 <= s.length <= 3 * 104s[i]is'(', or')'.
Solution
class Solution {
/**
* @param String $s
* @return Integer
*/
public function longestValidParentheses($s) {
$max = 0;
$left = 0;
$right = 0;
$n = strlen($s);
for ($i = 0; $i < $n; $i++) {
$ch = $s[$i];
if ($ch == '(') {
$left++;
} else {
$right++;
}
if ($right > $left) {
$left = 0;
$right = 0;
}
if ($left == $right) {
$max = max($max, $left + $right);
}
}
$left = 0;
$right = 0;
for ($i = $n - 1; $i >= 0; $i--) {
$ch = $s[$i];
if ($ch == '(') {
$left++;
} else {
$right++;
}
if ($left > $right) {
$left = 0;
$right = 0;
}
if ($left == $right) {
$max = max($max, $left + $right);
}
}
return $max;
}
}