DSA SheetEasy
EditorialPractice

HASHING › IMPLEMENTARY PROBLEMS

Substrings of Size Three with Distinct Characters

EasyEditorial · 5 minGenerated by gpt-5.6-luna · Aug 25

Open — the attempt gate is not wired up yet

This editorial is meant to unlock after you have run the problem at least once, with the worked solution behind one further deliberate click. That needs per-learner unlock state nothing stores today, so for now the whole article is open.

Try it yourself first →

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.

A string with a length-three sliding window moving one position to the rightShow a row of indexed characters from left to right with a highlighted window covering exactly three consecutive positions. Beside it, show a second highlighted window shifted one position to the right, sharing two characters with the first. Mark a window good when all three characters differ and mark it repeated when any two characters match. The picture makes clear that each starting index is a separate occurrence even when neighboring windows overlap.abcbdefg01234567current window: b c b — repeatednext window: c b d — goodEach starting position gives one length-three window; shift right by one, keeping thetwo-character overlap.

Approachone pass over the possible starting positions

  1. Set n to the string length and count to zero, because the answer is the number of qualifying windows rather than the windows themselves.
  2. 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.
  3. 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.
  4. 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.
  5. 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

MEASUREBOUNDWHY
TimeO(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.
SpaceO(1) extraThe 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.

Common mistakesthe two wrong code shapes that change the counted windows

Previous · Merge Similar Items