Partition the string in two parts such that both parts have at least k different characters | C ++ implementation of the above approach ; Function to find the partition of the string such that both parts have at least k different characters ; Length of the string ; To check if the current character is already found ; Count number of different characters in the left part ; If current character is not already found , increase cnt by 1 ; If count becomes equal to k , we 've  got the first part, therefore,  store current index and break the loop ; Increment i by 1 ; Clear the map ; Assign cnt as 0 ; If the current character is not already found , increase cnt by 1 ; If cnt becomes equal to k , the second part also have k different characters so break it ; If the second part has less than k different characters , then print " Not ▁ Possible " ; Otherwise print both parts ; Driver code ; Function call
#include <iostream> NEW_LINE #include <map> NEW_LINE using namespace std ; void division_of_string ( string str , int k ) { int n = str . size ( ) ; map < char , bool > has ; int ans , cnt = 0 , i = 0 ; while ( i < n ) { if ( ! has [ str [ i ] ] ) { cnt ++ ; has [ str [ i ] ] = true ; } if ( cnt == k ) { ans = i ; break ; } i ++ ; } i ++ ; has . clear ( ) ; cnt = 0 ; while ( i < n ) { if ( ! has [ str [ i ] ] ) { cnt ++ ; has [ str [ i ] ] = true ; } if ( cnt == k ) { break ; } i ++ ; } if ( cnt < k ) { cout << " Not ▁ possible " << endl ; } else { i = 0 ; while ( i <= ans ) { cout << str [ i ] ; i ++ ; } cout << endl ; while ( i < n ) { cout << str [ i ] ; i ++ ; } cout << endl ; } cout << endl ; } int main ( ) { string str = " geeksforgeeks " ; int k = 4 ; division_of_string ( str , k ) ; return 0 ; }