Question

How to find the length of the longest balanced parentheses (e.g. (()())) in C++

Answer 1

#include <iostream>
#include <stack>
#include <string>

int longestValidParentheses(const std::string& s) {
    std::stack<int> st;
    st.push(-1);  // base index
    int maxLen = 0;

    for (int i = 0; i < s.length(); i++) {
        if (s[i] == '(') {
            st.push(i);
        } else {
            st.pop();
            if (st.empty()) {
                st.push(i);  // new base
            } else {
                maxLen = std::max(maxLen, i - st.top());
            }
        }
    }

    return maxLen;
}

int main() {
    std::string s = "((()()))((("; // balanced parentheses = ((()())) then length = 8
    
    std::cout << longestValidParentheses(s) << std::endl;  
}

 
   
/*
run:
   
8

*/

 

70+ SQL courses for beginners and professionals

Answer 2

#include <iostream>
#include <vector>
#include <string>

int longestValidParentheses(std::string s) {
    int n = s.size();
    std::vector<int> dp(n, 0);
    int maxLen = 0;

    for (int i = 1; i < n; i++) {
        if (s[i] == ')') {
            int j = i - dp[i - 1] - 1;
            if (j >= 0 && s[j] == '(') {
                dp[i] = dp[i - 1] + 2;
                if (j - 1 >= 0) dp[i] += dp[j - 1];
            }
        }
        maxLen = std::max(maxLen, dp[i]);
    }

    return maxLen;
}

int main() {
    std::string s = "((()()))((("; // balanced parentheses = ((()())) then length = 8
    
    std::cout << longestValidParentheses(s) << std::endl;  
}

 
   
/*
run:
   
8

*/

 

70+ SQL courses for beginners and professionals