## Given a string(which has only lowercase allphabets) and a value k, write a function that will print the number of possible substrings that has exactly k distinct characters

### Example

**INPUT**

s = “abcd”

k = 3

**OUTPUT**

3

“abc” and “bcd” are the possible substrings

### Method 1

**Time Complexity : O(n*n*n)**

## Algorithm

**1.** Generate all possible substrings and check whether the substring has exactly k distinct characters or not.

### Method 2

In this method the main idea is to use hash table

**Time Complexity : O(n*n)**

## Algorithm

**1.** Build a count array for all lowercase alphabets

For every substring

**2.** If the current character is a new character for this substring, then increament distinct_count

**3.** If the distinct_count is equal to k, then increament result

## C++ Program

#include<bits/stdc++.h> using namespace std; int printKDistChars(string s, int k) { int n = s.length(); // Initialize output int output = 0; // Initialize a count array for lowercase alphabets int count[26]; // Consider all substrings beginning with // s[i] for (int i = 0; i < n; i++) { //For the count of disticnt characters int d_chars = 0; // making count array to 0 memset(count, 0, sizeof(count)); // Consider all substrings between s[i..j] for (int j=i; j<n; j++) { // If new character for this substring if (count[s[j] - 'a'] == 0) d_chars++; // Increment count of current character count[s[j] - 'a']++; // If distinct character count becomes k, // then increment result. if (d_chars == k) output++; } } return output; } int main() { string s = "abcd"; int k = 3; cout << "Total substrings with exactly " << k <<" distinct characters :" << printKDistChars(s, k) << endl; return 0; }

Try It