Given a string of lowercase alphabets, count all possible substrings (not necessarily distinct) that has exactly k distinct characters.
Examples:
Input: abc, k = 2
Output: 2
Possible substrings are {“ab”, “bc”}
Input: aba, k = 2
Output: 3
Possible substrings are {“ab”, “ba”, “aba”}
Input: aa, k = 1
Output: 3
Possible substrings are {“a”, “a”, “aa”}
Method 1 (Brute Force): If the length of string is n, then there can be n*(n+1)/2 possible substrings. A simple way is to generate all the substring and check each one whether it has exactly k unique characters or not. If we apply this brute force, it would take O(n*n) to generate all substrings and O(n) to do a check on each one. Thus overall it would go O(n*n*n)
Method 2: The problem can be solved in O(n*n). Idea is to maintain a hash table while generating substring and checking the number of unique characters using that hash table.
The implementation below assume that the input string contains only characters from ‘a’ to ‘z’.
Implementation
C++
#include<bits/stdc++.h>
using namespace std;
int countkDist(string str, int k)
{
int n = str.length();
int res = 0;
int cnt[26];
for (int i = 0; i < n; i++)
{
int dist_count = 0;
memset(cnt, 0, sizeof(cnt));
for (int j=i; j<n; j++)
{
if (cnt[str[j] - 'a'] == 0)
dist_count++;
cnt[str[j] - 'a']++;
if (dist_count == k)
res++;
if(dist_count > k) break;
}
}
return res;
}
int main()
{
string str = "abcbaa";
int k = 3;
cout << "Total substrings with exactly "
<< k <<" distinct characters :"
<< countkDist(str, k) << endl;
return 0;
}
|
Java
import java.util.Arrays;
public class CountKSubStr
{
int countkDist(String str, int k)
{
int res = 0;
int n = str.length();
boolean seen[] = new boolean[26];
for (int i = 0; i < n; i++)
{
int distCount = 0;
Arrays.fill(seen, false);
for (int j=i; j<n; j++)
{
if (!seen[str.charAt(j) - 'a'])
distCount++;
seen[str.charAt(j) - 'a'] = true;
if (distCount == k)
res++;
}
}
return res;
}
public static void main(String[] args)
{
CountKSubStr ob = new CountKSubStr();
String ch = "abcbaa";
int k = 3;
System.out.println("Total substrings with exactly " +
k + " distinct characters : "
+ ob.countkDist(ch, k));
}
}
|
Python 3
def countkDist(str1, k):
n = len(str1)
res = 0
cnt = [0] * 27
for i in range(0, n):
dist_count = 0
cnt = [0] * 27
for j in range(i, n):
if(cnt[ord(str1[j]) - 97] == 0):
dist_count += 1
cnt[ord(str1[j]) - 97] += 1
if(dist_count == k):
res += 1
if(dist_count > k):
break
return res
if __name__ == "__main__":
str1 = "abcbaa"
k = 3
print("Total substrings with exactly", k,
"distinct characters : ", end = "")
print(countkDist(str1, k))
|
C#
using System;
public class CountKSubStr
{
int countkDist(string str, int k)
{
int res = 0;
int n = str.Length;
int[] cnt = new int[26];
for (int i = 0; i < n; i++)
{
int dist_count = 0;
Array.Clear(cnt, 0,cnt.Length);
for (int j=i; j<n; j++)
{
if (cnt[str[j] - 'a'] == 0)
dist_count++;
cnt[str[j] - 'a']++;
if (dist_count == k)
res++;
}
}
return res;
}
public static void Main()
{
CountKSubStr ob = new CountKSubStr();
string ch = "abcbaa";
int k = 3;
Console.Write("Total substrings with exactly " +
k + " distinct characters : "
+ ob.countkDist(ch, k));
}
}
|
PHP
<?php
function countkDist($str, $k)
{
$res = 0;
$n = strlen($str);
$cnt = array();
for ($i = 0; $i < $n; $i++)
{
$dist_count = 0;
$cnt = array_fill(0, 0, true);
for ($j = $i; $j < $n; $j++)
{
if ($cnt[ord($str[$j]) - ord('a')] == 0)
$dist_count++;
$cnt[ord($str[$j]) - ord('a')]++;
if ($dist_count == $k)
$res++;
}
}
return $res;
}
{
$ch = "abcbaa";
$k = 3;
echo("Total substrings with exactly " .
$k . " distinct characters : "
. countkDist($ch, $k));
}
|
Javascript
<script>
function countkDist(str , k)
{
var res = 0;
var n = str.length;
var cnt = Array.from({length: 26}, (_, i) => 0);
for (i = 0; i < n; i++)
{
var dist_count = 0;
for (j=i; j<n; j++)
{
if (cnt[str.charAt(j).charCodeAt(0) - 'a'.charCodeAt(0)] == 0)
dist_count++;
cnt[str.charAt(j).charCodeAt(0) - 'a'.charCodeAt(0)]++;
if (dist_count == k)
res++;
}
}
return res;
}
var ch = "abcbaa";
var k = 3;
document.write("Total substrings with exactly " +
k + " distinct characters : "
+ countkDist(ch, k));
</script>
|
Output
Total substrings with exactly 3 distinct characters :8
Time Complexity: O(n*n)
Auxiliary Space: O(1), Only 26 size array is used, which can be considered constant space.
Efficient Approach: The idea is to count all the subarrays with at most K distinct characters and then subtract all the subarrays with atmost K – 1 characters. That leaves us with count of subarrays with exactly K distinct characters.
Below is the implementation of the above approach:
C++
#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;
int most_k_chars(string& s, int k)
{
if (s.size() == 0) {
return 0;
}
unordered_map<char, int> map;
int num = 0, left = 0;
for (int i = 0; i < s.size(); i++) {
map[s[i]]++;
while (map.size() > k) {
map[s[left]]--;
if (map[s[left]] == 0) {
map.erase(s[left]);
}
left++;
}
num += i - left + 1;
}
return num;
}
int exact_k_chars(string& s, int k)
{
return most_k_chars(s, k) - most_k_chars(s, k - 1);
}
int main()
{
string s1 = "pqpqs";
int k = 2;
cout << "Total substrings with exactly " << k
<< " distinct characters : "
<< exact_k_chars(s1, k) << endl;
string s2 = "aabab";
k = 2;
cout << "Total substrings with exactly " << k
<< " distinct characters : "
<< exact_k_chars(s2, k) << endl;
}
|
Java
import java.io.*;
import java.util.HashMap;
public class GFG
{
static int most_k_chars(String s, int k)
{
if (s.length() == 0) {
return 0;
}
HashMap<Character, Integer> map = new HashMap<>();
int num = 0, left = 0;
for (int i = 0; i < s.length(); i++) {
map.put(s.charAt(i),
map.getOrDefault(s.charAt(i), 0) + 1);
while (map.size() > k) {
map.put(s.charAt(left),
map.getOrDefault(s.charAt(left), 0)
- 1);
if (map.get(s.charAt(left)) == 0) {
map.remove(s.charAt(left));
}
left++;
}
num += i - left + 1;
}
return num;
}
static int exact_k_chars(String s, int k)
{
return most_k_chars(s, k) - most_k_chars(s, k - 1);
}
public static void main(String[] args)
{
String s1 = "pqpqs";
int k = 2;
System.out.println("Total substrings with exactly "
+ k + " distinct characters : "
+ exact_k_chars(s1, k));
String s2 = "aabab";
k = 2;
System.out.println("Total substrings with exactly "
+ k + " distinct characters : "
+ exact_k_chars(s2, k));
}
}
|
Python3
def most_k_chars(s, k):
if not s:
return 0
char_count = {}
num = 0
left = 0
for i in range(len(s)):
char_count[s[i]] = char_count.get(s[i], 0) + 1
while len(char_count) > k:
char_count[s[left]] -= 1
if char_count[s[left]] == 0:
char_count.pop(s[left])
left += 1
num += i - left + 1
return num
def exact_k_chars(s, k):
return most_k_chars(s, k) - most_k_chars(s, k - 1)
s1 = "pqpqs"
k = 2
print(f"Total substrings with exactly {k} distinct characters: {exact_k_chars(s1, k)}")
s2 = "aabab"
k = 2
print(f"Total substrings with exactly {k} distinct characters: {exact_k_chars(s2, k)}")
|
C#
using System;
using System.Collections.Generic;
class GFG {
static int most_k_chars(string s, int k)
{
if (s.Length == 0) {
return 0;
}
Dictionary<char, int> map
= new Dictionary<char, int>();
int num = 0, left = 0;
for (int i = 0; i < s.Length; i++) {
if (map.ContainsKey(s[i])) {
int val = map[s[i]];
map.Remove(s[i]);
map.Add(s[i], val + 1);
}
else
map.Add(s[i], 1);
while (map.Count > k) {
if (map.ContainsKey(s[left])) {
int val = map[s[left]];
map.Remove(s[left]);
map.Add(s[left], val - 1);
}
else
map.Add(s[left], -1);
if (map[s[left]] == 0) {
map.Remove(s[left]);
}
left++;
}
num += i - left + 1;
}
return num;
}
static int exact_k_chars(String s, int k)
{
return most_k_chars(s, k) - most_k_chars(s, k - 1);
}
public static void Main(string []args)
{
string s1 = "pqpqs";
int k = 2;
Console.WriteLine("Total substrings with exactly "
+ k + " distinct characters : "
+ exact_k_chars(s1, k));
string s2 = "aabab";
k = 2;
Console.WriteLine("Total substrings with exactly "
+ k + " distinct characters : "
+ exact_k_chars(s2, k));
}
}
|
Javascript
function most_k_chars(s, k) {
if (!s) {
return 0;
}
const char_count = {};
let num = 0;
let left = 0;
for (let i = 0; i < s.length; i++) {
char_count[s[i]] = (char_count[s[i]] || 0) + 1;
while (Object.keys(char_count).length > k) {
char_count[s[left]] -= 1;
if (char_count[s[left]] === 0) {
delete char_count[s[left]];
}
left += 1;
}
num += i - left + 1;
}
return num;
}
function exact_k_chars(s, k) {
return most_k_chars(s, k) - most_k_chars(s, k - 1);
}
const s1 = "pqpqs";
let k = 2;
console.log(`Total substrings with exactly ${k} distinct characters: ${exact_k_chars(s1, k)}`);
const s2 = "aabab";
k = 2;
console.log(`Total substrings with exactly ${k} distinct characters: ${exact_k_chars(s2, k)}`);
|
Output
Total substrings with exactly 2 distinct characters : 7
Total substrings with exactly 2 distinct characters : 9
Time Complexity: O(n)
Auxiliary Space: O(1)
If you like GeeksforGeeks and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the GeeksforGeeks main page and help other Geeks.
Feeling lost in the world of random DSA topics, wasting time without progress? It's time for a change! Join our DSA course, where we'll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 geeks!