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

 


Next > < Prev
Scroll to Top