3803. 统计残差前缀

题目描述

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

如果字符串 s 的某个前缀中 不同字符的数量 等于 len(prefix) % 3，则该前缀被称为残差前缀（residue）。

返回字符串 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，因此它是一个残差前缀。
前缀 "bob" 不满足条件。

因此，答案是 2。

提示：

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

解法

方法一：哈希表

我们用一个哈希表 \(\textit{st}\) 来记录当前前缀中出现过的不同字符的集合。遍历字符串 \(s\) 的每个字符 \(c\)，将其加入集合 \(\textit{st}\) 中，然后判断当前前缀的长度对 \(3\) 取模的结果是否等于集合 \(\textit{st}\) 的大小。如果相等，则说明当前前缀是一个残差前缀，答案加 \(1\)。

遍历结束后，返回答案即可。

时间复杂度 \(O(n)\)，空间复杂度 \(O(n)\)。其中 \(n\) 是字符串 \(s\) 的长度。

Python3JavaC++GoTypeScript

class Solution:
    def residuePrefixes(self, s: str) -> int:
        st = set()
        ans = 0
        for i, c in enumerate(s, 1):
            st.add(c)
            if len(st) == i % 3:
                ans += 1
        return ans

class Solution {
    public int residuePrefixes(String s) {
        Set<Character> st = new HashSet<>();
        int ans = 0;
        for (int i = 1; i <= s.length(); i++) {
            char c = s.charAt(i - 1);
            st.add(c);
            if (st.size() == i % 3) {
                ans++;
            }
        }
        return ans;
    }
}

class Solution {
public:
    int residuePrefixes(string s) {
        unordered_set<char> st;
        int ans = 0;
        for (int i = 1; i <= s.size(); i++) {
            char c = s[i - 1];
            st.insert(c);
            if (st.size() == i % 3) {
                ans++;
            }
        }
        return ans;
    }
};

func residuePrefixes(s string) int {
    st := make(map[rune]struct{})
    ans := 0
    for i, c := range s {
        idx := i + 1
        st[c] = struct{}{}
        if len(st) == idx%3 {
            ans++
        }
    }
    return ans
}

function residuePrefixes(s: string): number {
    const st = new Set<string>();
    let ans = 0;
    for (let i = 0; i < s.length; i++) {
        const c = s[i];
        st.add(c);
        if (st.size === (i + 1) % 3) {
            ans++;
        }
    }
    return ans;
}

3803. 统计残差前缀

题目描述

解法

方法一：哈希表

评论