Count ways to partition a string such that both parts have equal distinct characters | C ++ implementation to count the number of ways to partition the string such that each partition have same number of distinct characters in the string ; Function to count the distinct characters in the string ; Frequency of each character ; Loop to count the frequency of each character of the string ; If frequency is greater than 0 then the character occured ; Function to count the number of ways to partition the string such that each partition have same number of distinct character ; Loop to choose the partition index for the string ; Divide in two parts ; Check whether number of distinct characters are equal ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int distinctChars ( string s ) { int freq [ 26 ] = { 0 } ; int count = 0 ; for ( int i = 0 ; i < s . length ( ) ; i ++ ) freq [ s [ i ] - ' a ' ] ++ ; for ( int i = 0 ; i < 26 ; i ++ ) { if ( freq [ i ] > 0 ) count ++ ; } return count ; } int waysToSplit ( string s ) { int n = s . length ( ) ; int answer = 0 ; for ( int i = 1 ; i < n ; i ++ ) { string left = s . substr ( 0 , i ) ; string right = s . substr ( i , n - i ) ; if ( distinctChars ( left ) == distinctChars ( right ) ) answer ++ ; } return answer ; } int main ( ) { string s = " ababa " ; cout << waysToSplit ( s ) ; return 0 ; }