Easy

题目描述

给你一个只由小写英文字母组成的字符串 s。

如果 s 的一个前缀中不同字符的数量等于 len(prefix) % 3，则该前缀称为余数前缀。

返回 s 中余数前缀的数量。

字符串的前缀是从字符串开头开始并延伸到字符串内任意一点的非空子字符串。

示例 1：

输入：s = "abc"
输出：2
解释：
- 前缀 "a" 有 1 个不同字符，长度模 3 为 1，所以它是余数前缀。
- 前缀 "ab" 有 2 个不同字符，长度模 3 为 2，所以它是余数前缀。
- 前缀 "abc" 不满足条件。因此答案是 2。

示例 2：

输入：s = "dd"
输出：1
解释：
- 前缀 "d" 有 1 个不同字符，长度模 3 为 1，所以它是余数前缀。
- 前缀 "dd" 有 1 个不同字符，但长度模 3 为 2，所以它不是余数前缀。因此答案是 1。

示例 3：

输入：s = "bob"
输出：2
解释：
- 前缀 "b" 有 1 个不同字符，长度模 3 为 1，所以它是余数前缀。
- 前缀 "bo" 有 2 个不同字符，长度模 3 为 2，所以它是余数前缀。因此答案是 2。

提示：

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

解题思路

这道题要求我们统计字符串中满足特定条件的前缀数量。对于每个前缀，我们需要检查其不同字符数是否等于前缀长度对3取模的结果。

解题思路：

最直观的做法是模拟题目描述的过程：遍历字符串的每个位置，对于每个位置构成的前缀，计算其中不同字符的数量，然后检查是否等于前缀长度模3的值。

具体步骤：

  1. 遍历字符串的每个位置 i（从0开始）
  2. 对于当前位置，获取前缀 s[0…i]
  3. 使用集合（或哈希表）统计前缀中不同字符的数量
  4. 检查不同字符数是否等于 (i+1) % 3
  5. 如果满足条件，计数器加1

由于字符串长度最大只有100，这种暴力解法的时间复杂度是可以接受的。对于每个前缀，我们都重新计算不同字符数，虽然不是最优，但实现简单且符合题目要求。

优化思路：我们也可以在遍历过程中维护一个集合，动态添加字符并统计不同字符数，这样可以避免重复计算，但考虑到数据规模较小，简单的模拟方法已经足够。

代码实现

class Solution {
public:
    int residuePrefixes(string s) {
        int count = 0;
        int n = s.length();
        
        for (int i = 0; i < n; i++) {
            unordered_set<char> distinct;
            for (int j = 0; j <= i; j++) {
                distinct.insert(s[j]);
            }
            
            if (distinct.size() == (i + 1) % 3) {
                count++;
            }
        }
        
        return count;
    }
};

class Solution:
    def residuePrefixes(self, s: str) -> int:
        count = 0
        n = len(s)
        
        for i in range(n):
            distinct = set()
            for j in range(i + 1):
                distinct.add(s[j])
            
            if len(distinct) == (i + 1) % 3:
                count += 1
        
        return count

public class Solution {
    public int ResiduePrefixes(string s) {
        int count = 0;
        int n = s.Length;
        
        for (int i = 0; i < n; i++) {
            HashSet<char> distinct = new HashSet<char>();
            for (int j = 0; j <= i; j++) {
                distinct.Add(s[j]);
            }
            
            if (distinct.Count == (i + 1) % 3) {
                count++;
            }
        }
        
        return count;
    }
}

var residuePrefixes = function(s) {
    let count = 0;
    let distinctChars = new Set();
    
    for (let i = 0; i < s.length; i++) {
        distinctChars.add(s[i]);
        if (distinctChars.size === (i + 1) % 3) {
            count++;
        }
    }
    
    return count;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n²)，其中 n 是字符串长度。外层循环 n 次，内层循环最多 n 次
空间复杂度O(k)，其中 k 是不同字符的数量，最多为 26（小写字母数量）