# Count Number of Substrings with K Distinct Character’s

Difficulty Level Medium
Hash Hashing HashMap StringViews 1952

## Problem Statement

In the “Count Number of Substrings with K Distinct Character’s” problem, we have given a string “s” which has only lowercase alphabets and an integer value k. Write a program that will print the number of possible substrings that have exactly k distinct characters.

## Input Format

The first line containing a string “s”.

Second-line containing an integer value k.

## Output Format

The first and only one line containing an integer value “ans”. Where “ans” denotes the number of possible substrings that have exactly k distinct characters.

## Constraints

• 1<=|s|<=10^2
• s[i] must be a lower case English alphabet
• 1<=k<=26

## Example

```tutorialcup
5```
`7`

## Algorithm

The basic approach is to Generate all possible substrings and check whether the substring has exactly k distinct characters or not.

1. For every value of i in the range 0 to n-1 run second for loop where every value of j from i to n-1.

2. Define an unordered map to check the char is already occur or not.

3. If the current character is a new character for this substring, then increment temp.

4. After visiting the substring if the temp is equal to k, then increment result.

## Implementation

### C++ Program to Count Number of Substrings with K Distinct Character’s

```#include <bits/stdc++.h>
using namespace std;

int main()
{
string s;
cin>>s;
int k;
cin>>k;
int n=s.length();
int ans=0;
for(int i=0;i<n;i++)
{
for(int j=i;j<n;j++)
{
int temp=0;
unordered_map<char,int> m;
for(int l=i;l<=j;l++)
{
m[s[l]]++;
if(m[s[l]]==1)
{
temp++;
}
}
if(temp==k)
{
ans++;
}
}
}
cout<<ans<<endl;
return 0;
}
```

### Java Program to Count Number of Substrings with K Distinct Character’s

```import java.util.HashMap;
import java.util.Scanner;
class sum
{
public static void main(String[] args)
{
Scanner sr = new Scanner(System.in);
String s = sr.next();
int n = s.length();
int k = sr.nextInt();
int ans=0;
for(int i=0;i<n;i++)
{
for(int j=i;j<n;j++)
{
int temp=0;
HashMap<Character, Integer> m = new HashMap<>();
for(int l=i;l<=j;l++)
{
boolean check = m.containsKey(s.charAt(k));
if(!check)
{
temp++;
}
}
if(temp==k)
{
ans++;
}
}
}
System.out.println(ans);
}
}
```
```dancingcar
4```
`10`

## Complexity Analysis

### Time Complexity

O(n^3) where n is the size of the given string “s”. Here we visit every substring manually and update the answer as per the conditions.

### Space Complexity

O(n) because we use a map to check the char is present already or not.

Translate »