Count all indices of cyclic regular parenthesis | C ++ program for the above approach ; Function to find all indices which cyclic shift leads to get balanced parenthesis ; Create auxiliary array ; Finding prefix sum and minimum element ; Update the minimum element ; ChecK if count of ' ( ' and ' ) ' are equal ; Find count of minimum element ; Find the frequency of mn ; Return the count ; Driver Code ; Given string S ; Function Call
#include <bits/stdc++.h> NEW_LINE using namespace std ; int countCyclicShifts ( string & S , int n ) { int aux [ n ] = { 0 } ; for ( int i = 0 ; i < n ; ++ i ) { if ( S [ i ] == ' ( ' ) aux [ i ] = 1 ; else aux [ i ] = -1 ; } int mn = aux [ 0 ] ; for ( int i = 1 ; i < n ; ++ i ) { aux [ i ] += aux [ i - 1 ] ; mn = min ( mn , aux [ i ] ) ; } if ( aux [ n - 1 ] != 0 ) return 0 ; int count = 0 ; for ( int i = 0 ; i < n ; ++ i ) { if ( aux [ i ] == mn ) count ++ ; } return count ; } int main ( ) { string S = " ) ( ) ( " ; int N = S . length ( ) ; cout << countCyclicShifts ( S , N ) ; return 0 ; }