Count all indices of cyclic regular parenthesis | Java 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 ; length of the string S
import java . util . * ; class GFG { static int countCyclicShifts ( String S , int n ) { int [ ] aux = new int [ n ] ; for ( int i = 0 ; i < n ; ++ i ) { if ( S . charAt ( 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 = Math . 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 ; } public static void main ( String [ ] args ) { String S = " ) ( ) ( " ; int N = S . length ( ) ; System . out . print ( countCyclicShifts ( S , N ) ) ; } }