Substrings of Size Three with Distinct Characters

LeetCode 1876. Substrings of Size Three with Distinct Characters is one of the gentlest sliding window problems you will find. The window is always exactly three characters wide, and all you need to do is count how many of those windows contain no repeated characters. If you are new to sliding windows, this is a great place to start before tackling variable-width problems like Longest Substring Without Repeating Characters.

The problem

Given a string s, return the number of good substrings of length three. A string is good if there are no repeated characters in it.

Example: s = "xyzzaz". The substrings of length 3 are "xyz", "yzz", "zza", and "zaz". Only "xyz" has all distinct characters, so the answer is 1.

The first window, "xyz", passes because x, y, and z are all different. The remaining three windows each contain a repeated z, so they fail. That gives us a count of 1.

The brute force approach

The simplest approach is to extract every substring of length 3 and check whether its characters are all unique. You can use a set for the uniqueness check.

def count_good_substrings(s):
    count = 0
    for i in range(len(s) - 2):
        sub = s[i:i + 3]
        if len(set(sub)) == 3:
            count += 1
    return count

This works and is already efficient for this problem. Each iteration does a constant amount of work (building a set of at most 3 elements), so the total time is O(n). But let's think about why it works, because the reasoning generalizes to harder problems.

The key insight: fixed-size window

Since the window size is always 3, you do not need to grow or shrink it dynamically. You slide a fixed-size window across the string one position at a time. At each position, you check whether the three characters in the window are all distinct.

Checking for distinct characters

For a window of exactly 3 characters, the check is simple: put them in a set and see if the set has size 3. If any character is repeated, the set will be smaller.

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

That is an alternative to len(set(sub)) == 3. Both work in O(1) because the window is fixed at size 3. The direct comparison avoids allocating a set, but the set approach generalizes better to larger windows.

Visual walkthrough

Let's trace through "aababcabc" step by step. We slide the window from left to right and check each substring of length 3.

The first three windows ("aab", "aba", "bab") all have a repeated character. Starting at index 3, we hit "abc", "bca", "cab", and "abc" again, all of which have three distinct characters. The final count is 4.

The code

Here is a clean Python solution:

def count_good_substrings(s):
    count = 0
    for i in range(len(s) - 2):
        if s[i] != s[i + 1] and s[i + 1] != s[i + 2] and s[i] != s[i + 2]:
            count += 1
    return count

A few things to note about this approach:

1. The loop runs from 0 to len(s) - 3 (inclusive). Using range(len(s) - 2) achieves that because range stops before the upper bound.
2. We compare all three pairs of characters directly. For a window of size 3, there are exactly 3 pairs to check: (0,1), (1,2), and (0,2).
3. No extra data structures are needed. Each check is O(1), so the total is O(n).

Complexity analysis

Time: O(n). We visit each position in the string once and do O(1) work at each position (three comparisons or a set of size 3).

Space: O(1). No extra storage beyond a counter. Even the set version uses O(1) space because the set never holds more than 3 elements.

Both approaches are optimal. The input is a single string, so you cannot do better than O(n).

Edge cases to watch for

1. String shorter than 3 characters. If len(s) is 0, 1, or 2, there are no substrings of length 3. The loop simply does not execute, and the answer is 0.
2. All identical characters. For s = "aaaa", every window has repeated characters. The answer is 0.
3. All distinct characters. For s = "abcdef", every window of size 3 is good. The answer is len(s) - 2.
4. Exactly 3 characters. For s = "abc", there is exactly one window. If it has distinct characters, the answer is 1. Otherwise, 0.

The building blocks

This problem is a gentle introduction to the fixed-size sliding window pattern. Even though it is simple, it builds two reusable skills:

1. Fixed-window iteration

The act of iterating through all contiguous subarrays (or substrings) of a given size. The loop template is always the same: start at 0, stop at len(s) - k, and examine the k elements starting at each index.

for i in range(len(s) - k + 1):
    window = s[i:i + k]

This shows up in problems like finding the maximum average subarray, the minimum window sum, or any problem that asks you to evaluate every contiguous chunk of size k.

2. Uniqueness check in a fixed window

Deciding whether all elements in a small, fixed-size collection are distinct. For size 3, direct pairwise comparison works. For larger windows, you would switch to a set or a frequency counter. The pattern generalizes: as the window slides, you can maintain the set incrementally by removing the element that leaves and adding the element that enters.

These two pieces are the foundation of the sliding window pattern. In harder problems, the window size is variable and you need two pointers. But the core idea of sliding across the data and maintaining local state is identical.

From understanding to recall

Reading through a solution once is the easy part. The real challenge is being able to reproduce the approach from scratch when you encounter a new sliding window problem next week. Spaced repetition helps bridge that gap. You drill the fixed-window iteration template and the uniqueness check at increasing intervals, writing the code each time, until the pattern fires automatically.

Related posts

• Longest Substring Without Repeating Characters - The variable-width version of this problem, where the window grows and shrinks dynamically
• Contains Duplicate - The simplest set-based uniqueness problem, introducing the seen-set building block
• Group Anagrams - Another string problem that uses character frequency analysis as a core building block