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: using System ; using System . Collections . Generic ; class GFG { static bool isValidLen ( String s , int len , int k ) { int n = s . Length ; Dictionary < char , int > mp = new Dictionary < char , int > ( ) ; int right = 0 ; while ( right < len ) { if ( mp . ContainsKey ( s [ right ] ) ) { mp [ s [ right ] ] = mp [ s [ right ] ] + 1 ; } else { mp . Add ( s [ right ] , 1 ) ; } right ++ ; } if ( mp . Count <= k ) return true ; while ( right < n ) { if ( mp . ContainsKey ( s [ right ] ) ) { mp [ s [ right ] ] = mp [ s [ right ] ] + 1 ; } else { mp . Add ( s [ right ] , 1 ) ; } if ( mp . ContainsKey ( s [ right - len ] ) ) { mp [ s [ right - len ] ] = mp [ s [ right - len ] ] - 1 ; } if ( mp [ s [ right - len ] ] == 0 ) mp . Remove ( s [ right - len ] ) ; if ( mp . Count <= k ) return true ; right ++ ; } return mp . Count <= k ; } static int maxLenSubStr ( String s , int k ) { HashSet < char > uni = new HashSet < char > ( ) ; foreach ( char x in s . ToCharArray ( ) ) uni . Add ( x ) ; if ( uni . Count < 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 ; Console . Write ( maxLenSubStr ( s , k ) ) ; } }