# Count number of substrings with k distinct characaters

## 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;
}``````

Scroll to Top