C++ String Exercises: Length of the longest valid parentheses substring

Last update on December 20 2024 12:32:18 (UTC/GMT +8 hours)

Write a C++ program to find the length of the longest valid (correct-formed) parentheses substring of a given string.

Example-1:

Input: "[[]"

Output: 2

Note: The longest correct-formed parentheses substring is "[]".

Example-2:

Input: " [[]]]"

Output: 4

Note: The longest correct-formed parentheses substring is "[[]]".

Example-3:

Input: " ]]]][[[["

Output:

Note: No correct-formed parentheses substring.

Sample Solution:

C++ Code:

#include <iostream> // Input/output stream library
#include<algorithm> // Standard library for algorithms such as 'std::max'
#include <stack>    // Standard library for stack data structure
using namespace std; // Using the standard namespace

// Function to find the length of the longest valid parentheses substring
int longest_valid_Parentheses(string paren_str) {
    stack<int> temp; // Create a stack to store indices of opening brackets
    int result = 0; // Variable to store the length of the longest valid parentheses substring

    // Traverse the input parentheses string
    for (int i = 0; i < paren_str.size(); i++) {
        if (paren_str[i] == '[') {
            temp.push(i); // Push the index of the opening bracket onto the stack
        } else {
            // Check if the stack is not empty and the top of the stack contains an opening bracket
            if (!temp.empty() && paren_str[temp.top()] == '[') {
                temp.pop(); // Pop the matching opening bracket from the stack

                int last_pos = -1; // Initialize the last position variable

                // Update last position if the stack is not empty
                if (!temp.empty()) {
                    last_pos = temp.top();
                }

                int len = i - last_pos; // Calculate the length of the current valid substring
                result = max(result, len); // Update the result with the maximum valid length found
            } else {
                temp.push(i); // Push the current closing bracket's index onto the stack
            }
        }
    }
    return result; // Return the length of the longest valid parentheses substring
}

// Main function
int main() {
    // Test cases
    char main_str1[] = "[[]";
    cout << "Original Parentheses string: " << main_str1;
    cout << "\nLength of longest parentheses: " << longest_valid_Parentheses(main_str1);

    char main_str2[] = "[[]]]";
    cout << "\nOriginal Parentheses string: " << main_str2;
    cout << "\nLength of longest parentheses: " << longest_valid_Parentheses(main_str2);

    char main_str3[] = "]]]][[[[";
    cout << "\nOriginal Parentheses string: " << main_str3;
    cout << "\nLength of longest parentheses: " << longest_valid_Parentheses(main_str3);

    return 0; // Return 0 to indicate successful completion
}

Sample Output:

Original Parentheses string: [[]
Length of longest parentheses: 2
Original Parentheses string: [[]]]
Length of longest parentheses: 4
Original Parentheses string: ]]]][[[[
Length of longest parentheses: 0

Flowchart:

C++ Code Editor:

Click to Open Editor

Contribute your code and comments through Disqus.

Previous C++ Exercise: Combinations of brackets of pairs of parentheses.