Home » Interview Questions » String Interview Questions » Count number of substrings with k distinct characaters

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

READ  Longest Common Prefix using Sorting

 

How useful was this post?

Click on a star to rate it!

Average rating / 5. Vote Count

No votes so far! Be the first to rate this post.

As you found this post useful...

Follow us on social media!

We are sorry that this post was not useful for you!

Let us improve this post!

Tell us how we can improve this post?

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions