Table of Contents

## 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.