LC1876. 长度为三且字符不同的子字符串

LC1876. 长度为三且字符不同的子字符串

题目描述

如果一个字符串不含有任何重复字符，我们称这个字符串为 好 字符串。 给你一个字符串 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; } };