Substrings of Size Three With Distinct Characters (LC 1876)

The Problem

LeetCode 1876 — Substrings of Size Three With Distinct Characters

A string is good if it has no repeated characters. Given a string s, return the number of good substrings of length 3 in s. Note that if there are multiple occurrences of the same substring, every occurrence counts.

Input

"xyzzaz"

Output

1

Input

"aababcabc"

Output

4

Input

"abc"

Output

1

The Journey

Attempt by Attempt

Every step below was verified against a real input before moving on — not just described.

1 Over-Engineered Dynamic Window, Off-by-One on the Bounds 🐛 Buggy

function countGoodSubstrings(s: string): number {
  let i = 0, j = 0, count = 0;
  while (j < s.length) {
    // window is always exactly 3 — this grow/shrink dance is unnecessary
    while (j - i + 1 < 3) j++;
    while (j - i + 1 > 3) i++;
    const window = s.substring(i, j);
    if (new Set(window).size === 3) count++;
    i++; j++;
  }
  return count;
}

Treats this like a variable-size window that needs to grow and shrink — it doesn't, the window is always exactly 3. Worse, s.substring(i, j) is exclusive on the end, so it only ever checks a 2-character slice, never the full 3-character window.

The nested while loops are unnecessary ceremony for a window whose size never changes. But the real defect is the off-by-one: substring(i, j) should be substring(i, j + 1) to include the character at index j. A Set built from a 2-character string can never have size 3, so the validity check silently fails on every single window.

Proof — s = "xyzzaz":

i=0,j=2: window = s.substring(0,2) = "xy"  (missing s[2]='z') → Set size 2 ≠ 3 → not counted
i=1,j=3: window = s.substring(1,3) = "yz"  (missing s[3]='z') → Set size 2 ≠ 3 → not counted
i=2,j=4: window = s.substring(2,4) = "zz"  (missing s[4]='a') → Set size 1 ≠ 3 → not counted
i=3,j=5: window = s.substring(3,5) = "za"  (missing s[5]='z') → Set size 2 ≠ 3 → not counted
Returns 0   (WRONG — expected 1)

Fix →

Drop the unnecessary grow/shrink loops entirely — the window size never changes — and use substring(i, i + 3) so the full 3 characters are actually checked.

2 Correct Fixed-Size Window — But Allocates Every Iteration ✅ Correct

function countGoodSubstrings(s: string): number {
  let count = 0;
  for (let i = 0; i <= s.length - 3; i++) {
    const window = s.substring(i, i + 3);
    if (new Set(window).size === 3) count++;
  }
  return count;
}

Realized the window is fixed-size 3: a single loop, one window per iteration, no pointer bookkeeping at all. Correct — but allocates a new substring and a new Set on every single iteration, even though there are at most 3 characters to compare.

Proof — s = "xyzzaz":

i=0: "xyz" → distinct → count=1
i=1: "yzz" → z repeats → skip
i=2: "zza" → z repeats → skip
i=3: "zaz" → z repeats (pos 0 & 2) → skip
Returns 1 ✅ (correct, matches expected)

3 Final — No Allocations: Direct Pairwise Comparison ✅ ✅ Correct

// O(N) time, O(1) space — fixed-size window, no allocations
function countGoodSubstrings(s: string): number {
  let count = 0;

  for (let i = 0; i <= s.length - 3; i++) {
    // "3 choose 2" — all pairs among 3 elements, no Set/substring needed
    if (
      s[i] !== s[i + 1] && s[i + 1] !== s[i + 2] && s[i] !== s[i + 2]
    ) {
      count++;
    }
  }

  return count;
}

// "xyzzaz" → 1
console.log(countGoodSubstrings("xyzzaz")); // → 1

With only 3 characters, checking all 3 pairs directly — (i,i+1), (i+1,i+2), (i,i+2) — is all 'distinctness' means. No Set, no substring allocation, O(1) extra space per window.

Proof — s = "xyzzaz":

i=0: 'x'≠'y' && 'y'≠'z' && 'x'≠'z' → all true → count=1
i=1: 'y'≠'z' && 'z'≠'z' → false → skip
i=2: 'z'≠'z' → false → skip
i=3: 'z'≠'a' && 'a'≠'z' && 'z'≠'z' → false → skip
Returns 1 ✅ — same result as the Set version, zero allocations

Interactive

Window Visualizer

Watch the fixed 3-wide window slide across "xyzzaz" step-by-step.

i=0: window "xyz" → x, y, z all distinct → valid! count=1.

valid (counted) invalid

Lessons Learned

Key Takeaways

🪟

Fixed window size means no grow/shrink logic at all

If the problem hands you the window size up front, a single loop over the starting index is all you need — no left/right pointer bookkeeping.

✂️

Watch substring/slice bounds — exclusive ends are an easy off-by-one

s.substring(i, j) excludes index j. When you mean 'the next 3 characters starting at i', that's substring(i, i + 3), not substring(i, j) with j pointing at the last included index.

⚡

Direct comparisons beat Set/Map for tiny fixed windows

When a window size is fixed and tiny, look for the simplest possible check first — direct comparisons often beat data structures like Set/Map when there are only a handful of elements involved.

🔁

Get it correct first, then optimize

The Set-based version (Attempt 2) was correct before it was fast. Only after confirming the right answer did the pairwise-comparison optimization make sense to reach for.

Final Result

The Verified Solution

Fixed-size window + direct pairwise comparison — no Set, no substring allocation.

Final — Attempt 3

// O(N) time, O(1) space — fixed-size window, no allocations
function countGoodSubstrings(s: string): number {
  let count = 0;

  for (let i = 0; i <= s.length - 3; i++) {
    // "3 choose 2" — all pairs among 3 elements, no Set/substring needed
    if (
      s[i] !== s[i + 1] && s[i + 1] !== s[i + 2] && s[i] !== s[i + 2]
    ) {
      count++;
    }
  }

  return count;
}

// "xyzzaz" → 1
console.log(countGoodSubstrings("xyzzaz")); // → 1

Solution	Time	Space	Verified
Fixed Window + Set (Attempt 2)	O(N)	O(1)*	Correct, but allocates per window
Pairwise Comparison (Attempt 3) Optimized ✓	O(N)	O(1)	Zero allocations, matches Attempt 2's output

Reuse This

Template: Fixed-Size Sliding Window

The generic shape behind this solution — adapt it to any problem where the window width is given up front.

Pseudocode

function fixedSizeWindow(items, W):
    count = 0

    for i in 0..items.length - W:
        window = items[i .. i + W)          // always exactly W wide
        if isValid(window):                  // whatever the per-window condition is
            count++

    return count
    // No left/right pointers, no grow/shrink logic — the window's width never changes.

When to reach for this

The window size is fixed and given up front (e.g. "substrings of size K").

The trap this journey hit

When a window size is fixed and tiny, look for the simplest possible check first — direct comparisons often beat Set/Map for a handful of elements.

Test Yourself

Quiz: Check Your Understanding

Question 1 of 12 Score: 0

LeetCode 1876 always asks for substrings of length exactly 3. Why does this call for a fixed-size sliding window rather than a variable-size (grow/shrink) one? basic

When the window width is a constant given directly by the problem, there's no need for left/right pointer bookkeeping — a single loop advancing the start index by one each time is sufficient, since every window is already the same size. Treating the window as variable-size and adding grow/shrink while loops here is pure overhead, since the width never actually changes.

Keep Learning

Simple beats clever 🎉

One off-by-one bug, one unnecessary allocation — that's the real path from a first attempt to an optimal Fixed-Size Sliding Window solution.

Related: try LeetCode 3 (dynamic window, where you DO want a Set/Map) or LeetCode 2461 (fixed-size window + distinctness, one level up).

← Back to Sliding Window Solve on LeetCode ↗

Substrings of Size Three: From Over-Engineered to Optimal

LeetCode 1876 — Substrings of Size Three With Distinct Characters

Attempt by Attempt

Window Visualizer

Key Takeaways

Fixed window size means no grow/shrink logic at all

Watch substring/slice bounds — exclusive ends are an easy off-by-one

Direct comparisons beat Set/Map for tiny fixed windows

Get it correct first, then optimize

The Verified Solution

Template: Fixed-Size Sliding Window

Quiz: Check Your Understanding

Simple beats clever 🎉

Substrings of Size Three:
From Over-Engineered to Optimal