Count ways to partition a Binary String such that each substring contains exactly two 0 s | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int totalWays ( int n , string str ) { vector < int > IdxOf0s ; int cntWays = 1 ; for ( int i = 0 ; i < n ; i ++ ) { if ( str [ i ] == '0' ) { IdxOf0s . push_back ( i ) ; } } int M = IdxOf0s . size ( ) ; if ( M == 0 or M % 2 ) { return 0 ; } for ( int i = 2 ; i < M ; i += 2 ) { cntWays = cntWays * ( IdxOf0s [ i ] - IdxOf0s [ i - 1 ] ) ; } return cntWays ; } int main ( ) { string str = "00100" ; int n = str . length ( ) ; cout << totalWays ( n , str ) ; return 0 ; }