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