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