C++ Exercises: Length of the longest valid parentheses substring of a given string

C++ String: Exercise-18 with Solution

Write a C++ programming 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>

#include<algorithm>
#include <stack>
 
using namespace std;

int longest_valid_Parentheses(string paren_str) {
        stack<int> temp; 
        int result = 0;
        for(int i=0;i<paren_str.size();i++)
        {
            if(paren_str[i]=='[')
            {
                temp.push(i);
            }
            else
            {
                if(!temp.empty() && paren_str[temp.top()]=='[')
                {
                    temp.pop();
                    int last_pos=-1;
                    
                    if(!temp.empty())
                        last_pos=temp.top();
                    
                    int len = i-last_pos;
                    result = max(result,len); 
                }
                else
                {
                    temp.push(i);
                }  
            }
        }
        
        return result;
    }


int main()
{
  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;    
}

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:

Contribute your code and comments through Disqus.

Previous: Write a C++ program to find all combinations of well-formed brackets from a given paris of parentheses.