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 number of ways to partition the string such that each partition have same number of distinct character ; Prefix and suffix array for distinct character from start and end ; To check whether a character has appeared till ith index ; Calculating prefix array ; Character appears for the first time in string ; Character is visited ; Resetting seen for suffix calculation ; Calculating the suffix array ; Character appears for the first time ; This character has now appeared ; Loop to calculate the number partition points in the string ; Check whether number of distinct characters are equal ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int waysToSplit ( string s ) { int n = s . length ( ) ; int answer = 0 ; int prefix [ n ] = { 0 } ; int suffix [ n ] = { 0 } ; int seen [ 26 ] = { 0 } ; for ( int i = 0 ; i < n ; i ++ ) { int prev = ( i - 1 >= 0 ? prefix [ i - 1 ] : 0 ) ; if ( seen [ s [ i ] - ' a ' ] == 0 ) { prefix [ i ] += ( prev + 1 ) ; } else prefix [ i ] = prev ; seen [ s [ i ] - ' a ' ] = 1 ; } memset ( seen , 0 , sizeof ( seen ) ) ; suffix [ n - 1 ] = 0 ; for ( int i = n - 1 ; i >= 1 ; i -- ) { int prev = suffix [ i ] ; if ( seen [ s [ i ] - ' a ' ] == 0 ) { suffix [ i - 1 ] += ( prev + 1 ) ; } else suffix [ i - 1 ] = prev ; seen [ s [ i ] - ' a ' ] = 1 ; } for ( int i = 0 ; i < n ; i ++ ) { if ( prefix [ i ] == suffix [ i ] ) answer ++ ; } return answer ; } int main ( ) { string s = " ababa " ; cout << waysToSplit ( s ) ; return 0 ; }