Substrings of Size Three with Distinct Characters — Editorial

Opening the reading…

Intuitionwhy every length-three window can be judged on its own

A substring of length three is good exactly when its three characters are pairwise different. Once you choose its starting index i, there is no information from another window that can change this decision: compare s[i] with s[i + 1], s[i + 2], and compare the last two characters.

The only valid starting indices are 0 through n - 3. Move the start one position at a time, inspect the three characters beginning there, and increase the answer when all three comparisons succeed. Consecutive windows overlap, but that does not make them the same occurrence; every starting index must be counted separately.

Approachone pass over the possible starting positions

Set n to the string length and count to zero, because the answer is the number of qualifying windows rather than the windows themselves.

Loop with i + 2 < n, so the window s[i] through s[i + 2] stays inside the string; allowing i to reach n - 2 would read past the final character.

Check all three pairs among the window's characters: s[i] != s[i + 1], s[i] != s[i + 2], and s[i + 1] != s[i + 2]. Checking every pair is necessary because matching only adjacent characters misses a repeat between the first and third positions.

Increment count when all three comparisons are true, because that starting index contributes exactly one good occurrence and no other starting index should be counted in its place.

Return count after the loop, because every valid length-three substring has then been inspected exactly once and the required output is only the total.

Complexitythe window has fixed size three

MEASURE	BOUND	WHY
Time	O(n)	There are exactly max(0, n - 2) possible starting positions, and each position performs three constant-time comparisons. Windows overlap, but each starting position is processed once, so no substring is rescanned in a nested loop.
Space	O(1) extra	The solution stores only n, i, and count; the input string is not copied and the required returned integer is output, not working memory. The bound does not degrade for any input shape because the window remains fixed at three characters.

Here n is the length of the input string. The window size is the fixed constant 3.

Annotated solutionC++ · direct fixed-window scan · complete judge-ready implementation

CPPScan every valid length-three window and count it when its three pairwise comparisons all differ.

#include <string>
using namespace std;

class Solution {
public:
    int countGoodSubstrings(string s) {
        int n = s.size();
        int count = 0;

        for (int i = 0; i + 2 < n; ++i) {
            if (s[i] != s[i + 1] &&
                s[i] != s[i + 2] &&
                s[i + 1] != s[i + 2]) {
                ++count;
            }
        }

        return count;
    }
};

The loop condition is written as i + 2 < n because the rightmost character used by the window is s[i + 2]. The condition directly states that this character is valid, while still allowing the final window beginning at n - 3. The three comparisons are the complete definition of distinctness for exactly three characters, so no set or frequency table is needed.