human
Write me a code to longest substring with K unique characters using Binary Search and the other steps required given the following:
Longest substring with K unique characters using Binary Search | Function that returns True if there is a sub of length len with <= k unique characters.
Size of the.
Map to store the characters and their frequency.
Update the map for the first sub.
Check for the rest of the subs.
Add the new character.
Remove the first character of the previous window.
Update the map.
Function to return the length of the longest sub which has K unique characters.
Check if the complete contains K unique characters.
Size of the.
Apply binary search.
Driver code"
Solution in Python:
assistant
#Here is code to longest substring with K unique characters using Binary Search and the other steps required.
 def isValidLen ( s , lenn , k ) :
	n = len ( s )
	mp = dict ( )
	right = 0
	while ( right < lenn ) :
		mp [ s [ right ] ] = mp . get ( s [ right ] , 0 ) + 1
		right += 1
	if ( len ( mp ) <= k ) :
		return True
	while ( right < n ) :
		mp [ s [ right ] ] = mp . get ( s [ right ] , 0 ) + 1
		mp [ s [ right - lenn ] ] -= 1
		if ( mp [ s [ right - lenn ] ] == 0 ) :
			del mp [ s [ right - lenn ] ]
		if ( len ( mp ) <= k ) :
			return True
		right += 1
	return len ( mp ) <= k
def maxLenSubStr ( s , k ) :
	uni = dict ( )
	for x in s :
		uni [ x ] = 1
	if ( len ( uni ) < k ) :
		return - 1
	n = len ( s )
	lo = - 1
	hi = n + 1
	while ( hi - lo > 1 ) :
		mid = lo + hi >> 1
		if ( isValidLen ( s , mid , k ) ) :
			lo = mid
		else :
			hi = mid
	return lo
s = " aabacbebebe "
k = 3
print ( maxLenSubStr ( s , k ) )