Skip to content

3803. Count Residue Prefixes

Description

You are given a string s consisting only of lowercase English letters.

A prefix of s is called a residue if the number of distinct characters in the prefix is equal to len(prefix) % 3.

Return the count of residue prefixes in s.

A prefix of a string is a non-empty substring that starts from the beginning of the string and extends to any point within it.

 

Example 1:

Input: s = "abc"

Output: 2

Explanation:​​​​​​​

  • Prefix "a" has 1 distinct character and length modulo 3 is 1, so it is a residue.
  • Prefix "ab" has 2 distinct characters and length modulo 3 is 2, so it is a residue.
  • Prefix "abc" does not satisfy the condition. Thus, the answer is 2.

Example 2:

Input: s = "dd"

Output: 1

Explanation:

  • Prefix "d" has 1 distinct character and length modulo 3 is 1, so it is a residue.
  • Prefix "dd" has 1 distinct character but length modulo 3 is 2, so it is not a residue. Thus, the answer is 1.

Example 3:

Input: s = "bob"

Output: 2

Explanation:

  • Prefix "b" has 1 distinct character and length modulo 3 is 1, so it is a residue.
  • Prefix "bo" has 2 distinct characters and length mod 3 is 2, so it is a residue. Thus, the answer is 2.

 

Constraints:

  • 1 <= s.length <= 100
  • s contains only lowercase English letters.

Solutions

Solution 1: Hash Table

We use a hash table \(\textit{st}\) to record the set of distinct characters that have appeared in the current prefix. We iterate through each character \(c\) in the string \(s\), add it to the set \(\textit{st}\), and then check if the length of the current prefix modulo \(3\) equals the size of the set \(\textit{st}\). If they are equal, it means the current prefix is a residue prefix, and we increment the answer by \(1\).

After the iteration, we return the answer.

The time complexity is \(O(n)\) and the space complexity is \(O(n)\), where \(n\) is the length of the string \(s\).

1
2
3
4
5
6
7
8
9
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
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;
}

Comments