Maximize partitions such that no two substrings have any 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 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 Code
def maximum_partition ( strr ) : NEW_LINE INDENT i = 0 NEW_LINE j = 0 NEW_LINE k = 0 NEW_LINE c = 0 NEW_LINE r = 0 NEW_LINE m = { } NEW_LINE for i in range ( len ( strr ) - 1 , - 1 , - 1 ) : NEW_LINE INDENT if ( strr [ i ] not in m ) : NEW_LINE INDENT m [ strr [ i ] ] = i NEW_LINE DEDENT DEDENT i = 0 NEW_LINE k = m [ strr [ i ] ] NEW_LINE for i in range ( len ( strr ) ) : NEW_LINE INDENT if ( i <= k ) : NEW_LINE INDENT c = c + 1 NEW_LINE k = max ( k , m [ strr [ i ] ] ) NEW_LINE DEDENT else : NEW_LINE INDENT r = r + 1 NEW_LINE c = 1 NEW_LINE k = max ( k , m [ strr [ i ] ] ) NEW_LINE DEDENT DEDENT if ( c != 0 ) : NEW_LINE INDENT r = r + 1 NEW_LINE DEDENT return r NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT strr = " ababcbacadefegdehijhklij " NEW_LINE print ( maximum_partition ( strr ) ) NEW_LINE DEDENT