Substrings of Size K with Distinct Characters

Problem Statement:

A string is good if there are no repeated characters. Given a string s​​​​​, return the number of good substrings of length k in s​​​​​​. Note that if there are multiple occurrences of the same substring, every occurrence should be counted. A substring is a contiguous sequence of characters in a string.

Example 1:

Input: s = “xyzzaz” Output: 1 Explanation: There are 4 substrings of size 3: “xyz”, “yzz”, “zza”, and “zaz”. The only good substring of length 3 is “xyz”.

Example 2:

Input: s = “aababcabc” Output: 4 Explanation: There are 7 substrings of size 3: “aab”, “aba”, “bab”, “abc”, “bca”, “cab”, and “abc”. The good substrings are “abc”, “bca”, “cab”, and “abc”.

Solution:

1. Using HashMap:

TC: O(n * k)

• while loop runs n times, where n is the length of the string.
• Checking if the substring length is k and iterating over the frequency map values takes O(k) in the worst case, as there are at most k characters in the frequency map at any time.

class Solution {
    public int countGoodSubstrings(String s) {
        char[] charArray = s.toCharArray();
        HashMap<Character, Integer> fMap = new HashMap<>();
 
        int size = charArray.length;
        int start = 0, end = 0, k = 3;
        int ans = 0;
        
        while(end < size){
            fMap.put(charArray[end], fMap.getOrDefault(charArray[end], 0) + 1);
            
            if(k == end - start + 1){
                boolean isFreqOne = true;
                for(Integer freq: fMap.values()){
                    if(freq > 1){
                        isFreqOne = false;
                        break;
                    }
                }
                if(isFreqOne){
                    ans++;
                }
                fMap.put(charArray[start], fMap.get(charArray[start]) - 1);
                start++;
            }
            end++;
        }
        return ans;
    }
}

2. Using HashMap Optimized:

TC =O(n) Except while no other loop.

class Solution {
    public int countGoodSubstrings(String s) {
        char[] charArray = s.toCharArray();
        HashMap<Character, Integer> fMap = new HashMap<>();
 
        int size = charArray.length;
        int start = 0, end = 0, k = 3;
        int ans = 0;
        int uniqueFreqGtOne = 0;// Count of unique characters with frequency > 1
        
        while(end < size){
            fMap.put(charArray[end], fMap.getOrDefault(charArray[end], 0) + 1);
            
            if(fMap.get(charArray[end]) == 2) { 
	            uniqueFreqGtOne++;// Increment count if frequency becomes 2;
	        }
            //reached the window
            if(k == end - start + 1){
	            //if good string found increment the answer
	            if (uniqueFreqGtOne == 0) {
                    ans++;
                }
	            
                if (fMap.get(charArray[start]) == 2) {
                    uniqueFreqGtOne--; // Decrement count if frequency becomes 1
                }
	            
	            //update map before moving the start pointer.
                fMap.put(charArray[start], fMap.get(charArray[start]) - 1);                
                start++;
            }
            end++;
        }
        return ans;
    }
}