Length of the longest valid substring | C ++ program to find length of the longest valid substring ; method to get length of the longest valid ; Create a stack and push - 1 as initial index to it . ; Initialize result ; Traverse all characters of given string ; If opening bracket , push index of it ; If closing bracket , i . e . , str [ i ] = ' ) ' ; Pop the previous opening bracket 's index ; Check if this length formed with base of current valid substring is more than max so far ; If stack is empty . push current index as base for next valid substring ( if any ) ; Driver code ; Function call ; Function call
#include <bits/stdc++.h> NEW_LINE using namespace std ; int findMaxLen ( string str ) { int n = str . length ( ) ; stack < int > stk ; stk . push ( -1 ) ; int result = 0 ; for ( int i = 0 ; i < n ; i ++ ) { if ( str [ i ] == ' ( ' ) stk . push ( i ) ; else { if ( ! stk . empty ( ) ) { stk . pop ( ) ; } if ( ! stk . empty ( ) ) result = max ( result , i - stk . top ( ) ) ; else stk . push ( i ) ; } } return result ; } int main ( ) { string str = " ( ( ( ) ( ) " ; cout << findMaxLen ( str ) << endl ; str = " ( ) ( ( ) ) ) ) ) " ; cout << findMaxLen ( str ) << endl ; return 0 ; }