Number of balanced parenthesis substrings | CPP program to find number of balanced parenthesis sub strings ; Function to find number of balanced parenthesis sub strings ; To store required answer ; Vector to stores the number of balanced brackets at each depth . ; d stores checks the depth of our sequence For example level of ( ) is 1 and that of ( ( ) ) is 2. ; If open bracket increase depth ; If closing bracket ; Return the required answer ; Driver code ; Function call
#include <bits/stdc++.h> NEW_LINE using namespace std ; int Balanced_Substring ( string str , int n ) { int ans = 0 ; vector < int > arr ( n / 2 + 1 , 0 ) ; int d = 0 ; for ( int i = 0 ; i < n ; i ++ ) { if ( str [ i ] == ' ( ' ) d ++ ; else { if ( d == 1 ) { for ( int j = 2 ; j <= n / 2 + 1 && arr [ j ] != 0 ; j ++ ) arr [ j ] = 0 ; } ++ ans ; ans += arr [ d ] ; arr [ d ] ++ ; d -- ; } } return ans ; } int main ( ) { string str = " ( ) ( ) ( ) " ; int n = str . size ( ) ; cout << Balanced_Substring ( str , n ) ; return 0 ; }