Longest substring with K unique characters using Binary Search | Java implementation of the approach ; Function that returns true if there is a subString of length len with <= k unique characters ; Size of the String ; Map to store the characters and their frequency ; Update the map for the first subString ; Check for the rest of the subStrings ; Add the new character ; Remove the first character of the previous window ; Update the map ; Function to return the length of the longest subString which has K unique characters ; Check if the complete String contains K unique characters ; Size of the String ; Apply binary search ; Driver code
import java . util . * ; class GFG { static boolean isValidLen ( String s , int len , int k ) { int n = s . length ( ) ; Map < Character , Integer > mp = new HashMap < Character , Integer > ( ) ; int right = 0 ; while ( right < len ) { if ( mp . containsKey ( s . charAt ( right ) ) ) { mp . put ( s . charAt ( right ) , mp . get ( s . charAt ( right ) ) + 1 ) ; } else { mp . put ( s . charAt ( right ) , 1 ) ; } right ++ ; } if ( mp . size ( ) <= k ) return true ; while ( right < n ) { if ( mp . containsKey ( s . charAt ( right ) ) ) { mp . put ( s . charAt ( right ) , mp . get ( s . charAt ( right ) ) + 1 ) ; } else { mp . put ( s . charAt ( right ) , 1 ) ; } if ( mp . containsKey ( s . charAt ( right - len ) ) ) { mp . put ( s . charAt ( right - len ) , mp . get ( s . charAt ( right - len ) ) - 1 ) ; } if ( mp . get ( s . charAt ( right - len ) ) == 0 ) mp . remove ( s . charAt ( right - len ) ) ; if ( mp . size ( ) <= k ) return true ; right ++ ; } return mp . size ( ) <= k ; } static int maxLenSubStr ( String s , int k ) { Set < Character > uni = new HashSet < Character > ( ) ; for ( Character x : s . toCharArray ( ) ) uni . add ( x ) ; if ( uni . size ( ) < k ) return - 1 ; int n = s . length ( ) ; int lo = - 1 , hi = n + 1 ; while ( hi - lo > 1 ) { int mid = lo + hi >> 1 ; if ( isValidLen ( s , mid , k ) ) lo = mid ; else hi = mid ; } return lo ; } public static void main ( String [ ] args ) { String s = " aabacbebebe " ; int k = 3 ; System . out . print ( maxLenSubStr ( s , k ) ) ; } }