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


s = “abcd”
k = 3

“abc” and “bcd” are the possible substrings

Method 1

Time Complexity : O(n*n*n)


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)


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

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)
            // Increment count of current character
            count[s[j] - 'a']++;
            // If distinct character count becomes k,
            // then increment result.
            if (d_chars == k)
    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


Leave a Comment

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions
Core Java Interview Questions