Longest Valid Parentheses Problem


Description

LeetCode Problem 32.

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

Example 1:

1
2
3
Input: s = "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()".

Example 2:

1
2
3
Input: s = ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()".

Example 3:

1
2
Input: s = ""
Output: 0

Constraints:

  • 0 <= s.length <= 3 * 10^4
  • s[i] is ‘(‘, or ‘)’.


Sample C++ Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int longestValidParentheses(string s) {
        stack<int> stk;
        stk.push(-1);
        int ans = 0;
        for (int i = 0; i < s.size(); i++) {
            if (s[i] == '(') {
                stk.push(i);
            } else {
                stk.pop();
                if (stk.empty()) {
                    stk.push(i);
                } else {
                    ans = max(ans, i - stk.top());
                }
            }
        }
        return ans;
    }
};




Related Posts

Valid Number Problem

LeetCode 65. Given a string s, return true if s...

Text Justification Problem

LeetCode 68. Given an array of strings words and a...

Valid Number Problem

LeetCode 67. A robot is located at the top-left corner...

Length Of Last Word Problem

LeetCode 58. Given a string s consisting of some words...

Zigzag Conversion Problem

LeetCode 6. Write the code that will take a string...

Wildcard Matching Problem

LeetCode 44. Write the code that will take a string...