Longest substring with K unique characters using Binary Search | 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
function isValidLen ( s , len , k ) { var n = s . length ; var mp = new Map ( ) ; var right = 0 ; while ( right < len ) { if ( mp . has ( s [ right ] ) ) mp . set ( s [ right ] , mp . get ( s [ right ] ) + 1 ) else mp . set ( s [ right ] , 1 ) right ++ ; } if ( mp . size <= k ) return true ; while ( right < n ) { if ( mp . has ( s [ right ] ) ) mp . set ( s [ right ] , mp . get ( s [ right ] ) + 1 ) else mp . set ( s [ right ] , 1 ) if ( mp . has ( s [ right - len ] ) ) mp . set ( s [ right - len ] , mp . get ( s [ right - len ] ) - 1 ) if ( mp . has ( s [ right - len ] ) && mp . get ( s [ right - len ] ) == 0 ) mp . delete ( s [ right - len ] ) ; if ( mp . size <= k ) return true ; right ++ ; } return mp . size <= k ; } function maxLenSubStr ( s , k ) { var uni = new Set ( ) ; s . split ( ' ' ) . forEach ( x => { uni . add ( x ) ; } ) ; if ( uni . size < k ) return - 1 ; var n = s . length ; var lo = - 1 , hi = n + 1 ; while ( hi - lo > 1 ) { var mid = lo + hi >> 1 ; if ( isValidLen ( s , mid , k ) ) lo = mid ; else hi = mid ; } return lo ; } var s = " " ; var k = 3 ; document . write ( maxLenSubStr ( s , k ) ) ;