Longest sub | C ++ implementation to find the length of the longest substring having frequency of each character less than equal to k ; function to find the length of the longest substring having frequency of each character less than equal to k ; hash table to store frequency of each table ; ' start ' index of the current substring ; to store the maximum length ; traverse the string ' str ' ; get the current character as ' ch ' ; increase frequency of ' ch ' in ' freq [ ] ' ; if frequency of ' ch ' becomes more than ' k ' ; update ' maxLen ' ; decrease frequency of each character as they are encountered from the ' start ' index until frequency of ' ch ' is greater than ' k ' ; decrement frequency by '1' ; increment ' start ' ; update maxLen ; required length ; Driver program to test above
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define SIZE  26 NEW_LINE int longSubstring ( string str , int k ) { int freq [ SIZE ] ; memset ( freq , 0 , sizeof ( freq ) ) ; int start = 0 ; int maxLen = 0 ; char ch ; int n = str . size ( ) ; for ( int i = 0 ; i < n ; i ++ ) { ch = str [ i ] ; freq [ ch - ' a ' ] ++ ; if ( freq [ ch - ' a ' ] > k ) { if ( maxLen < ( i - start ) ) maxLen = i - start ; while ( freq [ ch - ' a ' ] > k ) { freq [ str [ start ] - ' a ' ] -- ; start ++ ; } } } if ( maxLen < ( n - start ) ) maxLen = n - start ; return maxLen ; } int main ( ) { string str = " babcaag " ; int k = 1 ; cout << " Length ▁ = ▁ " << longSubstring ( str , k ) ; return 0 ; }