Maximize partitions such that no two substrings have any common character | Java 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 code
import java . util . * ; class GFG { static int maximum_partition ( String str ) { int i = 0 , j = 0 , k = 0 ; int c = 0 , r = 0 ; HashMap < Character , Integer > m = new HashMap < > ( ) ; for ( i = str . length ( ) - 1 ; i >= 0 ; i -- ) { if ( ! m . containsKey ( str . charAt ( i ) ) ) { m . put ( str . charAt ( i ) , i ) ; } } i = 0 ; k = m . get ( str . charAt ( i ) ) ; for ( i = 0 ; i < str . length ( ) ; i ++ ) { if ( i <= k ) { c = c + 1 ; k = Math . max ( k , m . get ( str . charAt ( i ) ) ) ; } else { r = r + 1 ; c = 1 ; k = Math . max ( k , m . get ( str . charAt ( i ) ) ) ; } } if ( c != 0 ) { r = r + 1 ; } return r ; } public static void main ( String [ ] args ) { String str = " ababcbacadefegdehijhklij " ; System . out . print ( maximum_partition ( str ) ) ; } }