Find the longest substring with k unique characters in a given string | C ++ program to find the longest substring with k unique characters in a given string ; This function calculates number of unique characters using a associative array count [ ] . Returns true if no . of characters are less than required else returns false . ; Return true if k is greater than or equal to val ; Finds the maximum substring with exactly k unique chars ; Associative array to store the count of characters ; Traverse the string , Fills the associative array count [ ] and count number of unique characters ; If there are not enough unique characters , show an error message . ; Otherwise take a window with first element in it . start and end variables . ; Also initialize values for result longest window ; Initialize associative array count [ ] with zero ; put the first character ; Start from the second character and add characters in window according to above explanation ; Add the character ' s [ i ] ' to current window ; If there are more than k unique characters in current window , remove from left side ; Update the max window size if required ; Driver function
#include <iostream> NEW_LINE #include <cstring> NEW_LINE #define MAX_CHARS  26 NEW_LINE using namespace std ; bool isValid ( int count [ ] , int k ) { int val = 0 ; for ( int i = 0 ; i < MAX_CHARS ; i ++ ) if ( count [ i ] > 0 ) val ++ ; return ( k >= val ) ; } void kUniques ( string s , int k ) { int count [ MAX_CHARS ] ; memset ( count , 0 , sizeof ( count ) ) ; for ( int i = 0 ; i < n ; i ++ ) { if ( count [ s [ i ] - ' a ' ] == 0 ) u ++ ; count [ s [ i ] - ' a ' ] ++ ; } if ( u < k ) { cout << " Not ▁ enough ▁ unique ▁ characters " ; return ; } int curr_start = 0 , curr_end = 0 ; int max_window_size = 1 , max_window_start = 0 ; memset ( count , 0 , sizeof ( count ) ) ; count [ s [ 0 ] - ' a ' ] ++ ; for ( int i = 1 ; i < n ; i ++ ) { count [ s [ i ] - ' a ' ] ++ ; curr_end ++ ; while ( ! isValid ( count , k ) ) { count [ s [ curr_start ] - ' a ' ] -- ; curr_start ++ ; } if ( curr_end - curr_start + 1 > max_window_size ) { max_window_size = curr_end - curr_start + 1 ; max_window_start = curr_start ; } } cout << " Max ▁ substring ▁ is ▁ : ▁ " << s . substr ( max_window_start , max_window_size ) << " ▁ with ▁ length ▁ " << max_window_size << endl ; } int main ( ) { string s = " aabacbebebe " ; int k = 3 ; kUniques ( s , k ) ; return 0 ; }