Count ways to split a string into two subsets that are reverse of each other | C ++ program for the above approach ; Function to find the total number of ways to partitiaon the string into two subset satisfying the conditions ; Stores the resultant number of ways of splitting ; Iterate over the range [ 0 , 2 ^ N ] ; Traverse the string S ; If ith bit is set , then append the character S [ i ] to X ; Otherwise , append the character S [ i ] to Y ; Reverse the second string ; If X is equal to Y ; Return the total number of ways ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int countWays ( string S , int N ) { int ans = 0 ; for ( int mask = 0 ; mask < ( 1 << N ) ; mask ++ ) { string X , Y ; for ( int i = 0 ; i < N ; i ++ ) { if ( mask >> i & 1 ) { X += S [ i ] ; } else { Y += S [ i ] ; } } reverse ( Y . begin ( ) , Y . end ( ) ) ; if ( X == Y ) { ans ++ ; } } return ans ; } int main ( ) { string S = " mippiisssisssiipsspiim " ; int N = S . length ( ) ; cout << countWays ( S , N ) ; return 0 ; }