Longest substring where all the characters appear at least K times | Set 3 | C ++ program for the above approach ; Function to find the length of the longest substring ; Store the required answer ; Create a frequency map of the characters of the string ; Store the length of the string ; Traverse the string , s ; Increment the frequency of the current character by 1 ; Stores count of unique characters ; Find the number of unique characters in string ; Iterate in range [ 1 , unique ] ; Initialize frequency of all characters as 0 ; Stores the start and the end of the window ; Stores the current number of unique characters and characters occuring atleast K times ; New unique character ; New character which occurs atleast k times ; Expand window by incrementing end by 1 ; Check if this character is present atleast k times ; Check if this character is unique ; Shrink the window by incrementing start by 1 ; If there are curr_unique characters and each character is atleast k times ; Update the overall maximum length ; Print the answer ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int longestSubstring ( string s , int k ) { int ans = 0 ; int freq [ 26 ] = { 0 } ; int n = s . size ( ) ; for ( int i = 0 ; i < n ; i ++ ) freq [ s [ i ] - ' a ' ] ++ ; int unique = 0 ; for ( int i = 0 ; i < 26 ; i ++ ) if ( freq [ i ] != 0 ) unique ++ ; for ( int curr_unique = 1 ; curr_unique <= unique ; curr_unique ++ ) { memset ( freq , 0 , sizeof ( freq ) ) ; int start = 0 , end = 0 ; int cnt = 0 , count_k = 0 ; while ( end < n ) { if ( cnt <= curr_unique ) { int ind = s [ end ] - ' a ' ; if ( freq [ ind ] == 0 ) cnt ++ ; freq [ ind ] ++ ; if ( freq [ ind ] == k ) count_k ++ ; end ++ ; } else { int ind = s [ start ] - ' a ' ; if ( freq [ ind ] == k ) count_k -- ; freq [ ind ] -- ; if ( freq [ ind ] == 0 ) cnt -- ; start ++ ; } if ( cnt == curr_unique && count_k == curr_unique ) ans = max ( ans , end - start ) ; } } cout << ans ; } int main ( ) { string S = " aabbba " ; int K = 3 ; longestSubstring ( S , K ) ; return 0 ; }