Maximize partitions such that no two substrings have any common character | C ++ program to find the maximum number of partitions possible such that no two substrings have common character ; Function to calculate and return the maximum number of partitions ; r : Stores the maximum number of partitions k : Stores the ending index of the partition ; Stores the last index of every unique character of the string ; Traverse the string and store the last index of every character ; Store the last index of the first character from map ; Update K to find the end of partition ; Otherwise , the end of partition is found ; Increment r ; Update k for the next partition ; Add the last partition ; Driver Program
#include using namespace std ; int maximum_partition ( string str ) { int i = 0 , j = 0 , k = 0 ; int c = 0 , r = 0 ; unordered_map m ; for ( i = str . length ( ) - 1 ; i >= 0 ; i -- ) { if ( m [ str [ i ] ] == 0 ) { m [ str [ i ] ] = i ; } } i = 0 ; k = m [ str [ i ] ] ; for ( i = 0 ; i < str . length ( ) ; i ++ ) { if ( i <= k ) { c = c + 1 ; k = max ( k , m [ str [ i ] ] ) ; } else { r = r + 1 ; c = 1 ; k = max ( k , m [ str [ i ] ] ) ; } } if ( c != 0 ) { r = r + 1 ; } return r ; } int main ( ) { string str = " ababcbacadefegdehijhklij " ; cout << maximum_partition ( str ) ; }