Count substrings with each character occurring at most k times | CPP program to count number of substrings in which each character has count less than or equal to k . ; variable to store count of substrings . ; array to store count of each character . ; Initialize all characters count to zero . ; increment character count ; check only the count of current character because only the count of this character is changed . The ending point is incremented to current position only if all other characters have count at most k and hence their count is not checked . If count is less than k , then increase ans by 1. ; if count is less than k , then break as subsequent substrings for this starting point will also have count greater than k and hence are reduntant to check . ; return the final count of substrings . ; Driver code
#include <bits/stdc++.h> NEW_LINE using namespace std ; int findSubstrings ( string s , int k ) { int ans = 0 ; int cnt [ 26 ] ; int i , j , n = s . length ( ) ; for ( i = 0 ; i < n ; i ++ ) { memset ( cnt , 0 , sizeof ( cnt ) ) ; for ( j = i ; j < n ; j ++ ) { cnt [ s [ j ] - ' a ' ] ++ ; if ( cnt [ s [ j ] - ' a ' ] <= k ) ans ++ ; else break ; } } return ans ; } int main ( ) { string S = " aaabb " ; int k = 2 ; cout << findSubstrings ( S , k ) ; return 0 ; }