text: Longest substring with K unique characters using Binary Search | C ++ 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
code: #include <bits/stdc++.h> NEW_LINE using namespace std ; bool isValidLen ( string s , int len , int k ) { int n = s . size ( ) ; unordered_map < char , int > mp ; int right = 0 ; while ( right < len ) { mp [ s [ right ] ] ++ ; right ++ ; } if ( mp . size ( ) <= k ) return true ; while ( right < n ) { mp [ s [ right ] ] ++ ; mp [ s [ right - len ] ] -- ; if ( mp [ s [ right - len ] ] == 0 ) mp . erase ( s [ right - len ] ) ; if ( mp . size ( ) <= k ) return true ; right ++ ; } return mp . size ( ) <= k ; } int maxLenSubStr ( string s , int k ) { set < char > uni ; for ( auto x : s ) uni . insert ( x ) ; if ( uni . size ( ) < k ) return -1 ; int n = s . size ( ) ; 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 ; } int main ( ) { string s = " aabacbebebe " ; int k = 3 ; cout << maxLenSubStr ( s , k ) ; return 0 ; }