Count ways to partition a Binary String such that each substring contains exactly two 0 s | Java program for the above approach ; Function to find count of ways to partition the string such that each partition contains exactly two 0 s . ; Stores indices of 0 s in the given string . ; Store the count of ways to partition the string such that each partition contains exactly two 0 s . ; Iterate over each characters of the given string ; If current character is '0' ; Insert index ; Stores total count of 0 s in str ; Traverse the array , IdxOf0s [ ] ; Update cntWays ; Driver code
import java . util . * ; class GFG { static int totalWays ( int n , String str ) { ArrayList < Integer > IdxOf0s = new ArrayList < Integer > ( ) ; int cntWays = 1 ; for ( int i = 0 ; i < n ; i ++ ) { if ( str . charAt ( i ) == '0' ) { IdxOf0s . add ( i ) ; } } int M = IdxOf0s . size ( ) ; if ( ( M == 0 ) || ( ( M % 2 ) != 0 ) ) { return 0 ; } for ( int i = 2 ; i < M ; i += 2 ) { cntWays = cntWays * ( IdxOf0s . get ( i ) - IdxOf0s . get ( i - 1 ) ) ; } return cntWays ; } public static void main ( String [ ] args ) { String str = "00100" ; int n = str . length ( ) ; System . out . print ( totalWays ( n , str ) ) ; } }