Count Number of Substrings with K Distinct Character’s

Difficulty Level Medium
Frequently asked in LinkedIn Zoho
Hash Hashing HashMap StringViews 3464

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 ยป