Longest substring with atmost K characters from the given set of characters | C ++ implementation to find the longest substring in the string which contains atmost K characters from the given set of characters ; Function to find the longest substring in the string which contains atmost K characters from the given set of characters ; Base Condition ; Count for Characters from set in substring ; Two pointers ; Loop to iterate until right pointer is not equal to N ; Loop to increase the substring length until the characters from set are at most K ; Check if current pointer points a character from set ; If the count of the char is exceeding the limit ; update answer with substring length ; Increment the left pointer until the count is less than or equal to K ; If the character which comes out is normal character then decrement the count by 1 ; Driver Code ; Construction of set ; output result
#include <bits/stdc++.h> NEW_LINE using namespace std ; int maxNormalSubstring ( string & P , set < char > Q , int K , int N ) { if ( K == 0 ) return 0 ; int count = 0 ; int left = 0 , right = 0 ; int ans = 0 ; while ( right < N ) { while ( right < N && count <= K ) { if ( Q . find ( P [ right ] ) != Q . end ( ) ) { if ( count + 1 > K ) break ; else count ++ ; } right ++ ; if ( count <= K ) ans = max ( ans , right - left ) ; } while ( left < right ) { left ++ ; if ( Q . find ( P [ left - 1 ] ) != Q . end ( ) ) count -- ; if ( count < K ) break ; } } return ans ; } int main ( ) { string P = " giraffe " ; set < char > Q ; Q . insert ( ' a ' ) ; Q . insert ( ' f ' ) ; Q . insert ( ' g ' ) ; Q . insert ( ' r ' ) ; int K = 2 ; int N = P . length ( ) ; cout << maxNormalSubstring ( P , Q , K , N ) ; return 0 ; }