LeetCode Hot 100 P32 Longest Valid Parentheses

---

Timeline

Timeline

2026-03-21

init

Dynamic Programming, Stack

---

Problem:

P416 Partition Equal Subset Sum

https://leetcode.cn/problems/longest-valid-parentheses/description/?envType=study-plan-v2&envId=top-100-liked

• Simulate with a stack, mark all positions of unmatched parentheses as 1,
  • For example:()(()the mark is [0, 0, 1, 0, 0]
  • Another example:)()((())the mark is [1, 0, 0, 1, 0, 0, 0, 0]
• After such processing, this problem becomesfinding the length of the longest consecutive zeros

#include <string>
#include <vector>
#include <stack>

using std::string;
using std::vector;
using std::stack;

class Solution {
    public:
        int longestValidParentheses(string s)
        {
                int i, j, n = s.size();
                int max_len = 0;
                stack<int> stk;
                vector<int> arr(n, 0);

                for (i = 0; i < n; i++) {
                        if (s[i] == '(') {
                                stk.push(i);
                        } else {
                                if (stk.empty())
                                        arr[i] = 1;
                                else
                                        stk.pop();
                        }
                }
                while (!stk.empty()) { //unmatched parentheses
                        arr[stk.top()] = 1;
                        stk.pop();
                }
                // Find the longest consecutive zeros
                i = 0;
                while (i < n) {
                        if (arr[i] == 0) {
                                j = i;

                                while (j < n && arr[j] == 0)
                                        j++;

                                max_len = std::max(max_len, j - i);
                                i = j + 1;
                        } else {
                                i++;
                        }
                }

                return max_len;
        }
};