Count Number of Substrings with K Distinct Character’s

Difficulty Level Medium
Frequently asked in LinkedIn Zoho
Hash Hashing HashMap String

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.

See also
Given two unsorted arrays find all pairs whose sum is x

Space Complexity

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