Aniket Vaishnav

Posted on

# Substring of length k with k-1 distinct elements

## Problem Statement

Given a String S consisting only lowercase alphabets and an integer K. Find the count of all substrings of length K which have exactly K-1 distinct characters.

Example 1:

``````Input:
S = "abcc"
K = 2
Output:
1
Explanation:
Possible substrings of length K = 2 are
ab : 2 distinct characters
bc : 2 distinct characters
cc : 1 distinct character
Only one valid substring exists {"cc"}.
``````

Example 2:

``````Input:
S = "aabab"
K = 3
Output :
3
Explanation:
Possible substrings of length K = 3 are
aab : 2 distinct characters
aba : 2 distinct characters
bab : 2 distinct characters.
All of these Substrings are a possible answer,
so the count is 3.
``````

## Solution

The problem could be approached with help of two pointers as the length of the expected string is constant K. So the window between the two pointers let's say left(l) and right(*r) is the same and just needs to slide this window one by one character.
The sliding will encounter the elimination of the previous character and the inclusion of a new character. According to this, character map should be updated. The character map is the map maintaining, characters with their frequency in the window.

``````class Solution {
static int countOfSubstrings(String S, int k) {
char[] s = S.toCharArray();
int l = 0;
int r = 0;
int cnt = 0;
HashMap<Character, Integer> map = new HashMap<>();

// initial map setting for window
for(; r < k; r++) {
map.put(s[r], map.getOrDefault(s[r], 0) + 1);
}

int res = map.size() == k - 1? 1 : 0;

for (; r < s.length; r++, l++) {
map.put(s[r], map.getOrDefault(s[r], 0) + 1);

// removing character
if( map.get(s[l]) == 1 ) {
// remove character
// if it was the only character
// into the window
map.remove(s[l]);
} else {
map.put(s[l], map.get(s[l]) - 1);
}
if(map.size() == k-1) res++;
}

return res;
}
}
``````