32. Longest valid bracket (difficult stack string)

32. Longest valid bracket

Give you one that only contains ‘(’ and ‘)’ String , Find the longest effective （ The format is correct and continuous ） The length of the bracket substring .

Example 1：

Input ：s = “(()”
Output ：2
explain ： The longest valid bracket substring is “()”
Example 2：

Input ：s = “)()())”
Output ：4
explain ： The longest valid bracket substring is “()()”
Example 3：

Input ：s = “”
Output ：0

Tips ：

0 <= s.length <= 3 * 104
s[i] by ‘(’ or ‘)’

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/longest-valid-parentheses
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

analysis

Matching questions like parentheses is easy to think of using stacks or dynamic programming , Here, we use the stack and the method of traversing twice in positive and negative order , Dynamic planning can refer to the official solution .
Method 1 ： Stack
The idea is to traverse each character of the string , Store all in the stack “(” The subscript , Every encounter “)” Just pop A subscript , At this time, the difference between the subscript at the top of the stack and the subscript currently traversed is the length of the current continuous valid parentheses , It should be noted that the currently continuous valid parentheses are not necessarily the longest , It needs to be compared with the longest length recorded before .
Because we need to use the digital record length at the top of the stack , So the preprocessing stack stores -1.
Method 2 ： Two traversal
The optimization space complexity is O(1)
Ideas ： First , The left and right parentheses of valid parentheses must be equal ; secondly , Separate right parentheses （ No left parentheses match ） It must not be counted in valid brackets , And if there is such a right parenthesis , Can be used as continuous valid parentheses “ Separator ”.
Then we can consider this , Using two variables left and right Record the number of left and right parentheses respectively , Traversing the string from left to right , Valid parentheses must start with an open parenthesis , End with a right parenthesis , So all valid parentheses begin left Must be greater than right Of , When left = right when , Record the length of the current longest valid bracket （ Use the recorded length and 2 * right comparison ）, And then continue to traverse , If you encounter right > left The situation of , Explain the appearance of “ Separator ”, The preceding valid parentheses cannot be continuous with the following , Make left = right = 0, Re recording .
For the above ideas , It can be found that for “(()” This situation starts with multiple left parentheses and ends with fewer right parentheses , Because no left = right appear , So we can't get the valid bracket length , In this case, you can use reverse traversal , First record the number of right parentheses and then the number of left parentheses .

Answer key （Java）

Method 1 ：

class Solution {
    
    public int longestValidParentheses(String s) {
    
        int ans = 0;
        Deque<Integer> stack = new LinkedList<Integer>();
        stack.push(-1);
        for (int i = 0; i < s.length(); i++) {
    
            if (s.charAt(i) == '(') {
    
                stack.push(i);
            } else {
    
                stack.pop();
                if (stack.isEmpty()) {
    
                    stack.push(i);
                } else {
    
                    ans = Math.max(ans, i - stack.peek());
                }
            }
        }
        return ans;
    }
}

Method 2 ：

class Solution {
    
    public int longestValidParentheses(String s) {
    
        int left = 0, right = 0, ans = 0;
        for (int i = 0; i < s.length(); i++) {
    // positive 
            if (s.charAt(i) == '(') {
    
                left++;
            } else {
    
                right++;
            }
            if (left == right) {
    
                ans = Math.max(ans, right * 2);
            } else if (right > left) {
    
                left = right = 0;
            }
        }
        left = right = 0;
        for (int i = s.length() - 1; i >= 0; i--) {
    // reverse 
            if (s.charAt(i) == ')') {
    
                right++;
            } else {
    
                left++;
            }
            if (left == right) {
    
                ans = Math.max(ans, left * 2);
            } else if (left > right) {
    
                left = right = 0;
            }
        }
        return ans;
    }
}