Count number of substrings having at least K distinct characters

Count number of substrings having at least K distinct characters

Given a string S consisting of N characters and a positive integer K, the task is to count the number of substrings having at least K distinct characters.

Examples:

Input: S = “abcca”, K = 3
Output: 4
Explanation:
The substrings that contain at least K(= 3) distinct characters are:

1. “abc”: Count of distinct characters = 3.
2. “abcc”: Count of distinct characters = 3.
3. “abcca”: Count of distinct characters = 3.
4. “bcca”: Count of distinct characters = 3.

Therefore, the total count of substrings is 4.

Input: S = “abcca”, K = 4
Output: 0

Naive Approach: The simplest approach to solve the given problem is to generate all substrings of the given string and count those substrings that have at least K distinct characters in them. After checking for all the substrings, print the total count obtained as the result.
Time Complexity: O(N³)
Auxiliary Space: O(256)

Efficient Approach: The above approach can also be optimized by using the concept of Sliding Window and Hashing. Follow the steps below to solve the problem:

• Initialize a variable, say ans as 0 to store the count of substrings having at least K distinct characters.
• Initialize two pointers, begin and end to store the starting and ending point of the sliding window.
• Initialize a HashMap, say M to store the frequency of characters in the window.
• Iterate until end is less than N, and perform the following steps:
  • Include the character at the end of the window, by incrementing the value of S[end] in M by 1.
  • Iterate until the size of M becomes less than K, and perform the following steps:
    • Remove the characters from the starting of the window by decrementing the value of S[begin] in M by 1.
    • If its frequency becomes 0, then erase it from the map M.
    • Count all the substrings starting from begin till N by incrementing ans by (N – end + 1).
• After completing the above steps, print the value of ans as the result.

Below is the implementation of the above approach:

C++

#include <bits/stdc++.h> using namespace std;    void atleastkDistinctChars(string s, int k) {          int n = s.size();             unordered_map<char, int> mp;                  int begin = 0, end = 0;             int ans = 0;                  while (end < n) {                              char c = s[end];         mp++;                     end++;                              while (mp.size() >= k) {                                          char pre = s[begin];             mp[pre]--;                                          if (mp[pre] == 0) {                 mp.erase(pre);             }                             ans += s.length() - end + 1;             begin++;         }     }             cout << ans; }    int main() {     string S = "abcca";     int K = 3;     atleastkDistinctChars(S, K);        return 0; }

Time Complexity: O(N)
Auxiliary Space: O(256)

Attention reader! Don’t stop learning now. Get hold of all the important DSA concepts with the DSA Self Paced Course at a student-friendly price and become industry ready.

Let's block ads! (Why?)

Original page link

Best Cool Tech Gadgets

Top favorite technology gadgets