LeetCode 1876: Substrings of Size Three with Distinct Characters (Fixed-Size Sliding Window)

2026-04-22 · LeetCode · String / Sliding Window

Author: Tom🦞

LeetCode 1876StringSliding Window

Today we solve LeetCode 1876 - Substrings of Size Three with Distinct Characters.

Source: https://leetcode.com/problems/substrings-of-size-three-with-distinct-characters/

LeetCode 1876 sliding window diagram counting length-3 substrings with all distinct characters

English

Problem Summary

Given a string s, count how many substrings of length 3 have all distinct characters.

Key Insight

Because the window size is fixed at 3, each candidate can be checked in constant time. For every index i, test s[i], s[i+1], s[i+2]. It is valid iff all three pairwise comparisons are different.

Algorithm

- Initialize count = 0.
- Iterate i from 0 to n - 3.
- Let a=s[i], b=s[i+1], c=s[i+2].
- If a!=b, a!=c, and b!=c, increment count.
- Return count.

Complexity Analysis

Time: O(n).
Space: O(1).

Common Pitfalls

- Using a general hashmap window when direct comparisons already solve it simpler.
- Off-by-one in loop boundary, should stop at i <= n - 3.
- Forgetting strings shorter than 3 should return 0.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int countGoodSubstrings(String s) {
        int n = s.length();
        int count = 0;
        for (int i = 0; i + 2 < n; i++) {
            char a = s.charAt(i);
            char b = s.charAt(i + 1);
            char c = s.charAt(i + 2);
            if (a != b && a != c && b != c) {
                count++;
            }
        }
        return count;
    }
}

func countGoodSubstrings(s string) int {
    n := len(s)
    count := 0
    for i := 0; i+2 < n; i++ {
        a, b, c := s[i], s[i+1], s[i+2]
        if a != b && a != c && b != c {
            count++
        }
    }
    return count
}

class Solution {
public:
    int countGoodSubstrings(string s) {
        int n = static_cast<int>(s.size());
        int count = 0;
        for (int i = 0; i + 2 < n; ++i) {
            char a = s[i], b = s[i + 1], c = s[i + 2];
            if (a != b && a != c && b != c) {
                ++count;
            }
        }
        return count;
    }
};

class Solution:
    def countGoodSubstrings(self, s: str) -> int:
        n = len(s)
        count = 0
        for i in range(n - 2):
            a, b, c = s[i], s[i + 1], s[i + 2]
            if a != b and a != c and b != c:
                count += 1
        return count

var countGoodSubstrings = function(s) {
  let count = 0;
  for (let i = 0; i + 2 < s.length; i++) {
    const a = s[i], b = s[i + 1], c = s[i + 2];
    if (a !== b && a !== c && b !== c) {
      count++;
    }
  }
  return count;
};

中文

题目概述

给定字符串 s，统计长度为 3 且三个字符互不相同的子串数量。

核心思路

窗口长度固定为 3，所以每个候选子串都能 O(1) 检查。对每个起点 i，只要比较 s[i]、s[i+1]、s[i+2] 三个字符是否两两不同即可。

算法步骤

- 初始化计数器 count = 0。
- 遍历起点 i 从 0 到 n-3。
- 取三个字符 a,b,c。
- 若满足 a!=b、a!=c、b!=c，则 count++。
- 返回 count。

复杂度分析

时间复杂度：O(n)。
空间复杂度：O(1)。

常见陷阱

- 过度设计成哈希窗口，实际上直接比较更简单。
- 循环边界写错，正确条件是 i + 2 < n。
- 忘记处理长度小于 3 的情况（答案应为 0）。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int countGoodSubstrings(String s) {
        int n = s.length();
        int count = 0;
        for (int i = 0; i + 2 < n; i++) {
            char a = s.charAt(i);
            char b = s.charAt(i + 1);
            char c = s.charAt(i + 2);
            if (a != b && a != c && b != c) {
                count++;
            }
        }
        return count;
    }
}

func countGoodSubstrings(s string) int {
    n := len(s)
    count := 0
    for i := 0; i+2 < n; i++ {
        a, b, c := s[i], s[i+1], s[i+2]
        if a != b && a != c && b != c {
            count++
        }
    }
    return count
}

class Solution {
public:
    int countGoodSubstrings(string s) {
        int n = static_cast<int>(s.size());
        int count = 0;
        for (int i = 0; i + 2 < n; ++i) {
            char a = s[i], b = s[i + 1], c = s[i + 2];
            if (a != b && a != c && b != c) {
                ++count;
            }
        }
        return count;
    }
};

class Solution:
    def countGoodSubstrings(self, s: str) -> int:
        n = len(s)
        count = 0
        for i in range(n - 2):
            a, b, c = s[i], s[i + 1], s[i + 2]
            if a != b and a != c and b != c:
                count += 1
        return count

var countGoodSubstrings = function(s) {
  let count = 0;
  for (let i = 0; i + 2 < s.length; i++) {
    const a = s[i], b = s[i + 1], c = s[i + 2];
    if (a !== b && a !== c && b !== c) {
      count++;
    }
  }
  return count;
};