LeetCode 1876 - Substrings of Size Three with Distinct Characters

LeetCode Problem 1876

Difficulty: 🟢 Easy
Topics: Hash Table, String, Sliding Window, Counting

Solution

Problem Understanding

The problem asks us to count how many substrings of length exactly three contain only distinct characters. A substring is a continuous portion of the string, so for every position in the string, we can examine the next three consecutive characters and determine whether all three are different.

For example, in the string "xyzzaz", the possible substrings of length three are:

• "xyz"
• "yzz"
• "zza"
• "zaz"

Only "xyz" contains three unique characters, so the answer is 1.

The input is a single string s consisting only of lowercase English letters. The length of the string is between 1 and 100, which is very small. Even relatively inefficient approaches would work comfortably within the constraints. However, the problem is designed to test understanding of substring traversal and simple sliding window techniques.

The expected output is a single integer representing how many substrings of size three are "good", meaning no repeated characters appear inside the substring.

Several edge cases are important to recognize early:

• If the string length is less than 3, no valid substring of size three exists, so the answer must be 0.
• A substring like "aaa" is not good because all characters repeat.
• A substring like "aba" is also invalid because the character 'a' appears twice.
• Multiple identical good substrings should all be counted separately. For example, "abcabc" contains "abc" twice, and both occurrences count.

Approaches

Brute Force Approach

The brute force method examines every substring of length three individually. For each starting index i, we extract the substring s[i:i+3] and check whether its characters are all distinct.

One straightforward way to verify distinctness is to place the three characters into a set. Since sets automatically remove duplicates, a substring is good if the set size equals 3.

This approach is correct because every possible substring of length three is checked exactly once, and each substring is evaluated independently.

Although this solution is already efficient enough for the given constraints, it still repeatedly creates temporary substrings and sets. For larger window sizes or larger inputs, this repeated work could become less efficient.

Optimal Sliding Window Approach

The key observation is that every substring we care about has a fixed size of exactly three. Instead of creating many temporary substrings, we can directly compare the three characters in the current window.

A substring of length three is good if:

• s[i] != s[i+1]
• s[i] != s[i+2]
• s[i+1] != s[i+2]

This avoids creating extra data structures and keeps the solution extremely lightweight.

This is considered a sliding window approach because we conceptually move a fixed-size window of length three across the string one position at a time.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(1)	Checks every length-3 substring using a temporary set
Optimal	O(n)	O(1)	Uses direct character comparisons inside a fixed sliding window

Algorithm Walkthrough

1. Initialize a counter variable good_count to 0. This variable stores how many valid substrings we have found.
2. Traverse the string from index 0 to len(s) - 3. Each index represents the starting position of a substring of length three.
3. For each position i, examine the three characters:

• s[i]
• s[i + 1]
• s[i + 2]

4. Check whether all three characters are distinct by performing pairwise comparisons:

• s[i] != s[i + 1]
• s[i] != s[i + 2]
• s[i + 1] != s[i + 2]

5. If all three conditions are true, increment good_count by 1.
6. Continue sliding the window one position to the right until all possible substrings of size three have been checked.
7. Return good_count after the loop finishes.

Why it works

The algorithm works because every substring of length three appears exactly once as the window slides across the string. The pairwise comparisons guarantee that no two characters inside the window are equal. Since a length-three substring contains exactly three positions, confirming all pairwise inequalities is sufficient to prove all characters are distinct.

Python Solution

class Solution:
    def countGoodSubstrings(self, s: str) -> int:
        good_count = 0

        for i in range(len(s) - 2):
            if (
                s[i] != s[i + 1]
                and s[i] != s[i + 2]
                and s[i + 1] != s[i + 2]
            ):
                good_count += 1

        return good_count

The implementation begins by initializing good_count, which tracks the number of valid substrings.

The loop runs from 0 to len(s) - 3, inclusive. Using range(len(s) - 2) ensures that indices i + 1 and i + 2 always remain valid.

Inside the loop, the code directly compares the three characters in the current window. If all comparisons indicate distinct characters, the substring is good, so the counter increases by one.

Finally, the method returns the total count after all windows have been processed.

Go Solution

func countGoodSubstrings(s string) int {
    goodCount := 0

    for i := 0; i < len(s)-2; i++ {
        if s[i] != s[i+1] &&
            s[i] != s[i+2] &&
            s[i+1] != s[i+2] {
            goodCount++
        }
    }

    return goodCount
}

The Go implementation follows the same logic as the Python solution. Since strings in Go can be indexed directly by byte, and the problem guarantees lowercase English letters, character access is straightforward and safe.

No additional arrays, slices, or maps are needed. The solution uses constant extra space and performs only simple character comparisons.

Worked Examples

Example 1

Input:

s = "xyzzaz"

The algorithm checks every substring of size three.

Index	Substring	Distinct Characters?	Count
0	"xyz"	Yes	1
1	"yzz"	No	1
2	"zza"	No	1
3	"zaz"	No	1

Final answer:

1

Example 2

Input:

s = "aababcabc"

Index	Substring	Distinct Characters?	Count
0	"aab"	No	0
1	"aba"	No	0
2	"bab"	No	0
3	"abc"	Yes	1
4	"bca"	Yes	2
5	"cab"	Yes	3
6	"abc"	Yes	4

Final answer:

4

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each length-3 window is processed exactly once
Space	O(1)	Only a few variables are used

The algorithm scans the string one time from left to right. Each iteration performs a constant amount of work consisting of three character comparisons. Therefore, the running time grows linearly with the string length.

The memory usage remains constant because no extra data structures proportional to the input size are allocated.

Test Cases

solution = Solution()

assert solution.countGoodSubstrings("xyzzaz") == 1  # example case
assert solution.countGoodSubstrings("aababcabc") == 4  # repeated valid substrings

assert solution.countGoodSubstrings("abc") == 1  # exactly one valid substring
assert solution.countGoodSubstrings("aaa") == 0  # all characters identical
assert solution.countGoodSubstrings("aba") == 0  # first and last characters repeat

assert solution.countGoodSubstrings("ab") == 0  # string shorter than 3
assert solution.countGoodSubstrings("a") == 0  # minimum length input

assert solution.countGoodSubstrings("abcdef") == 4  # every window is valid
assert solution.countGoodSubstrings("zzzzzz") == 0  # no valid substrings

assert solution.countGoodSubstrings("abca") == 2  # overlapping valid substrings
assert solution.countGoodSubstrings("abcabc") == 4  # repeated valid patterns

Test	Why
"xyzzaz"	Verifies the first example
"aababcabc"	Verifies repeated valid substrings
"abc"	Smallest possible valid substring
"aaa"	All characters identical
"aba"	Repeated character with different middle character
"ab"	Input shorter than required window size
"a"	Minimum constraint boundary
"abcdef"	Every window should be valid
"zzzzzz"	No valid substrings exist
"abca"	Tests overlapping windows
"abcabc"	Ensures duplicate good substrings are counted separately

Edge Cases

One important edge case occurs when the input string length is smaller than three. Since the problem requires substrings of size exactly three, no valid substring can exist. A careless implementation might attempt invalid indexing operations. The loop condition range(len(s) - 2) naturally prevents iteration in this situation, so the method correctly returns 0.

Another important case is when all characters are identical, such as "aaaaaa". Every window contains repeated characters, so the answer should remain zero. The pairwise comparison checks correctly reject every substring because at least one equality condition fails.

A more subtle edge case involves overlapping substrings. For example, "abcdef" contains "abc", "bcd", "cde", and "def", all of which are valid. The implementation correctly slides the window by one position at a time, ensuring overlapping windows are evaluated independently and counted separately.

A final edge case involves repeated valid substrings, such as "abcabc". Even though "abc" appears twice, the problem states that each occurrence must be counted. Since the algorithm processes windows by position rather than by unique substring value, both occurrences are included in the final count correctly.