Substrings of Size Three with Distinct Characters

The task is to determine the count of unique substrings of length three that can be generated from a given string, ensuring that each substring comprises distinct characters.

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 = "abcdef"
   Output: 6
   Explanation: There are 4 substrings of size 3: "abc", "bcd", "cde", and "def".
   The good substrings are "abc", "bcd", "cde", and "def".

Example 2:

   Input: s = "xyyxz"
   Output: 2
   Explanation: There are 3 substrings of size 3: "xyy", "yyx", and "yxz".
   The only good substring of length 3 is "yxz".

Java implementation:

    public int generateSubstringsWithDistinctCharacters(String s) {
        int n = s.length();
        
        Map<Character,Integer> map = new HashMap<>();
        int right =0;
        int left=0;
        int count = 0;
        while(right<n){
            map.put(s.charAt(right),map.getOrDefault(s.charAt(right),0)+1);
            if(right-left+1 == 3){
                if(map.size()==3){
                    count++;
                }
            }else if(right-left+1>3){
                if(map.get(s.charAt(left))==1){
                    map.remove(s.charAt(left));
                }else{
                    map.put(s.charAt(left),map.get(s.charAt(left))-1);
                }
                if(map.size()==3){
                    count++;
                }

                left++;
            }
            right++;
        }
        return count;
    }

C++ implementation:

#include <string>
#include <unordered_map>
using namespace std;

int generateSubstringsWithDistinctCharacters(string s) {
    int n = s.length();
    unordered_map<char, int> map;
    int right = 0;
    int left = 0;
    int count = 0;
    
    while (right < n) {
        map[s[right]]++;
        if (right - left + 1 == 3) {
            if (map.size() == 3) {
                count++;
            }
        } else if (right - left + 1 > 3) {
            map[s[left]]--;
            if (map[s[left]] == 0) {
                map.erase(s[left]);
            }
            if (map.size() == 3) {
                count++;
            }
            left++;
        }
        right++;
    }
    return count;
}

Python implementation:

def generate_substrings_with_distinct_characters(s: str) -> int:
    n = len(s)
    char_count = {}
    right =
    left = 0
    count = 0
    
    while right < n:
        char_count[s[right]] = char_count.get(s[right], 0) + 1
        if right - left + 1 == 3:
            if len(char_count) == 3:
                count += 1
        elif right - left + 1 > 3:
            char_count[s[left]] -= 1
            if char_count[s[left]] == 0:
                del char_count[s[left]]
            if len(char_count) == 3:
                count += 1
            left += 1
        right += 1
    
    return count

1. It initializes variables `n`, `right`, `left`, and `count`. `n` stores the length of the input string `s`. `right` and `left` represent pointers for the sliding window technique used to iterate through the string. `count` stores the count of valid substrings found.

2. It initializes a HashMap named `map` to store characters along with their frequencies encountered  within the sliding window.

3. The method iterates through the string using a sliding window approach. At each step:

   - It updates the character count in the HashMap for the current character at the right pointer.

   - If the size of the current substring is equal to 3:

     - If the HashMap contains exactly 3 different characters, increment the count.

   - If the size exceeds 3:

     - It adjusts the left pointer, removing the character at the left end of the window from the HashMap.  If the count of that character becomes zero, it removes it entirely.

     - If the HashMap contains exactly 3 different characters after the adjustment, increment the count.   

4. The method returns the final count.

This method efficiently solves the problem by utilizing the sliding window technique and a HashMap to keep track of character frequencies within the current substring.