# Substrings of Size Three with Distinct Characters
**Difficulty:** EASY
[External](https://leetcode.com/problems/substrings-of-size-three-with-distinct-characters)
Canonical: https://scaleengineer.com/dsa/problems/substrings-of-size-three-with-distinct-characters
**Patterns:** [Sliding Window](https://scaleengineer.com/dsa/patterns/sliding-window), [Counting](https://scaleengineer.com/dsa/patterns/counting)
**Data structures:** Hash Table, String
**Companies:** [Accenture](https://scaleengineer.com/companies/accenture), [Visa](https://scaleengineer.com/companies/visa), [Quora](https://scaleengineer.com/companies/quora)
---
## Problem
A string is **good** if there are no repeated characters.

Given a string `s`​​​​​, return _the number of **good substrings** of length **three** 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".

**Constraints:**

* `1 <= s.length <= 100`
* `s`​​​​​​ consists of lowercase English letters.

# Approaches
## General Substring Check with Set
This approach iterates through the string to generate all substrings of length three. For each substring, a helper function is used to determine if it's "good". This helper function leverages a `HashSet` to efficiently check for duplicate characters. While this method is versatile and can be adapted for substrings of any length, it introduces some overhead for the specific case of length three.
**Time:** O(N), where `N` is the length of the string `s`. The loop runs `N-2` times. Inside the loop, creating a substring of length 3 and checking its uniqueness with a `HashSet` takes constant time (`O(1)`), as the size is fixed at 3. · **Space:** O(1). Although a `HashSet` and a new `String` object are created in each iteration, their size is constant (at most 3 elements), so the space complexity does not scale with the input size `N`.
**Pros:** The logic is clear and easy to reason about.; The helper function `isGood` is modular and can be reused to check substrings of any length `k`.
**Cons:** Incurs overhead from creating new `String` and `HashSet` objects in every iteration.; For a fixed small size like 3, this is less performant than direct character comparisons.
### Explanation
The main logic iterates from the beginning of the string up to the third-to-last character to define the starting point of each potential substring.
In each step, a substring of length 3 is extracted.
This substring is passed to a helper function, `isGood`.
The `isGood` function creates a `HashSet` of characters. It then iterates through the three characters of the substring. For each character, it tries to add it to the set. The `add` method of a `HashSet` returns `false` if the element is already present. If a duplicate is found, `isGood` immediately returns `false`. If all characters are added successfully, it means they are all unique, and the function returns `true`.
A counter is incremented for every "good" substring found.
Finally, the total count is returned.
```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    private boolean isGood(String sub) {
        Set<Character> charSet = new HashSet<>();
        for (char c : sub.toCharArray()) {
            if (!charSet.add(c)) { // Found a duplicate
                return false;
            }
        }
        return true;
    }

    public int countGoodSubstrings(String s) {
        int n = s.length();
        if (n < 3) {
            return 0;
        }
        int count = 0;
        for (int i = 0; i <= n - 3; i++) {
            // Extracting substring can have overhead
            String sub = s.substring(i, i + 3);
            if (isGood(sub)) {
                count++;
            }
        }
        return count;
    }
}
```
### Algorithm
- Initialize a counter `count` to 0.
- If the string length `n` is less than 3, return 0.
- Iterate with an index `i` from 0 to `n - 3`.
- In each iteration, extract the substring of length 3 starting at `i`.
- Check if this substring has unique characters using a `HashSet`:
    - Create an empty `HashSet`.
    - For each character in the substring, try to add it to the set.
    - If `add` ever returns `false`, the substring is not good.
    - If all characters are added successfully, the substring is good.
- If the substring is good, increment `count`.
- Return `count` after the loop.

## Optimized Sliding Window with Direct Comparison
This is the most efficient approach for this problem. It uses a single pass through the string, conceptually similar to a sliding window of size three. Instead of creating substrings and using data structures, it directly accesses and compares the characters at the relevant indices.
**Time:** O(N), where `N` is the length of the string `s`. We perform a single pass through the string. Each step involves a constant number of character accesses and comparisons. · **Space:** O(1). This approach uses only a few variables for the loop index and counter, requiring constant extra space.
**Pros:** Extremely fast and efficient due to direct memory access and simple comparisons.; Minimal memory overhead.; Very simple to implement.
**Cons:** The comparison logic `(c1 != c2 && c2 != c3 && c1 != c3)` is hardcoded for size 3. Generalizing it to an arbitrary size `k` would require a more complex approach.
### Explanation
The algorithm iterates through the string just once, from the first character up to the character at index `n-3`. The loop variable `i` represents the start of a 3-character window.
In each iteration, it looks at the characters `s.charAt(i)`, `s.charAt(i+1)`, and `s.charAt(i+2)`.
It performs a simple and direct check: `s.charAt(i) != s.charAt(i+1)`, `s.charAt(i+1) != s.charAt(i+2)`, and `s.charAt(i) != s.charAt(i+2)`.
If all three conditions are true, it means the three characters in the current window are distinct, and a counter is incremented.
This avoids the overhead of creating new string objects or auxiliary data structures like sets for each window.
```java
class Solution {
    public int countGoodSubstrings(String s) {
        int count = 0;
        int n = s.length();
        if (n < 3) {
            return 0;
        }
        // Iterate up to the start of the last possible 3-char substring
        for (int i = 0; i <= n - 3; i++) {
            char c1 = s.charAt(i);
            char c2 = s.charAt(i + 1);
            char c3 = s.charAt(i + 2);
            
            // Direct comparison of the three characters
            if (c1 != c2 && c2 != c3 && c1 != c3) {
                count++;
            }
        }
        return count;
    }
}
```
### Algorithm
- Initialize a counter `count` to 0.
- If the string length `n` is less than 3, return 0.
- Iterate with an index `i` from 0 to `n - 3`.
- In each iteration, get the three characters in the current window: `c1 = s.charAt(i)`, `c2 = s.charAt(i+1)`, `c3 = s.charAt(i+2)`.
- Compare the characters directly: if `c1 != c2` AND `c2 != c3` AND `c1 != c3`, then the substring is good.
- If the substring is good, increment `count`.
- Return `count` after the loop.

# Solutions
### Java

```java
class Solution { public int countGoodSubstrings ( String s ) { int count = 0 , n = s . length (); for ( int i = 0 ; i < n - 2 ; ++ i ) { char a = s . charAt ( i ), b = s . charAt ( i + 1 ), c = s . charAt ( i + 2 ); if ( a != b && a != c && b != c ) { ++ count ; } } return count ; } }
```

### CPP

```cpp
class Solution { public: int countGoodSubstrings ( string s ) { int ans = 0 ; int n = s . length (); for ( int l = 0 , r = 0 , mask = 0 ; r < n ; ++ r ) { int x = s [ r ] - 'a' ; while (( mask >> x & 1 ) == 1 ) { int y = s [ l ++ ] - 'a' ; mask ^= 1 << y ; } mask |= 1 << x ; ans += r - l + 1 >= 3 ? 1 : 0 ; } return ans ; } };
```

### Python

```python
class Solution : def countGoodSubstrings ( self , s : str ) -> int : count , n = 0 , len ( s ) for i in range ( n - 2 ): count += s [ i ] != s [ i + 1 ] and s [ i ] != s [ i + 2 ] and s [ i + 1 ] != s [ i + 2 ] return count
```