LeetCode 1876、长度为三且字符不同的子字符串

如果一个字符串不含有任何重复字符，我们称这个字符串为好字符串。

给你一个字符串 s ，请你返回 s 中长度为 3 的 好子字符串 的数量。

注意，如果相同的好子字符串出现多次，每一次都应该被记入答案之中。

子字符串 是一个字符串中连续的字符序列。

示例 1：

**输入：**s = "xyzzaz" **输出：**1 **解释：**总共有 4 个长度为 3 的子字符串："xyz"，"yzz"，"zza" 和 "zaz" 。唯一的长度为 3 的好子字符串是 "xyz" 。

示例 2：

**输入：**s = "aababcabc" **输出：**4 **解释：**总共有 7 个长度为 3 的子字符串："aab"，"aba"，"bab"，"abc"，"bca"，"cab" 和 "abc" 。好子字符串包括 "abc"，"bca"，"cab" 和 "abc" 。

提示：

1 <= s.length <= 100
s 只包含小写英文字母。

二、参考代码

Python

# 题目：LC1876. 长度为三且字符不同的子字符串
# 难度：简单
# 作者：许老师-闭着眼睛学数理化
# 算法：固定滑窗
# 代码看不懂的地方，请直接在群上提问

class Solution:
    def countGoodSubstrings(self, s: str) -> int:
        ans = 0
        cnt = collections.Counter(s[:3])

        # 计算第一个窗口的结果
        if len(cnt) == 3:
            ans += 1

        for right, ch in enumerate(s[3:], 3):
            # A1
            cnt[ch] += 1

            # A2
            left = right-3
            left_ch = s[left]
            cnt[left_ch] -= 1
            if cnt[left_ch] == 0:
                del cnt[left_ch]

            # A3
            if len(cnt) == 3:
                ans += 1

        return ans

Java

class Solution {
    public int countGoodSubstrings(String s) {
        if (s.length() < 3) {
            return 0;
        }

        int ans = 0;
        HashMap<Character, Integer> cnt = new HashMap<>();

        // 初始化第一个窗口的字符计数
        for (int i = 0; i < 3; i++) {
            cnt.put(s.charAt(i), cnt.getOrDefault(s.charAt(i), 0) + 1);
        }

        // 计算第一个窗口的结果
        if (cnt.size() == 3) {
            ans++;
        }

        for (int right = 3; right < s.length(); right++) {
            // A1
            char ch = s.charAt(right);
            cnt.put(ch, cnt.getOrDefault(ch, 0) + 1);

            // A2
            int left = right - 3;
            char leftCh = s.charAt(left);
            cnt.put(leftCh, cnt.get(leftCh) - 1);
            if (cnt.get(leftCh) == 0) {
                cnt.remove(leftCh);
            }

            // A3
            if (cnt.size() == 3) {
                ans++;
            }
        }

        return ans;
    }
}

C++

class Solution {
public:
    int countGoodSubstrings(std::string s) {
        if (s.length() < 3) {
            return 0;
        }

        int ans = 0;
        std::unordered_map<char, int> cnt;

        // 初始化第一个窗口的字符计数
        for (int i = 0; i < 3; i++) {
            cnt[s[i]]++;
        }

        // 计算第一个窗口的结果
        if (cnt.size() == 3) {
            ans++;
        }

        for (int right = 3; right < s.length(); right++) {
            // A1
            char ch = s[right];
            cnt[ch]++;

            // A2
            int left = right - 3;
            char leftCh = s[left];
            cnt[leftCh]--;
            if (cnt[leftCh] == 0) {
                cnt.erase(leftCh);
            }

            // A3
            if (cnt.size() == 3) {
                ans++;
            }
        }

        return ans;
    }
};