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.
Link to problem statement:: https://practice.geeksforgeeks.org/problems/substrings-of-length-k-with-k-1-distinct-elements/1
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.
Expected Time Complexity: O(|S|)
Expected Auxiliary Space: O(1)
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;
// gradually incrementing window
for (; r < s.length; r++, l++) {
// adding the character
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;
}
}
Top comments (0)