﻿ C++ - Length of the longest valid parentheses substring

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

## C++ String: Exercise-18 with Solution

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:

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

Next C++ Exercise: Reverse only the vowels of a given string.

What is the difficulty level of this exercise?

﻿