Welcome to Subscribe On Youtube

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$.

  • 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;
    }
};


  • 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


  • 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;
}

All Problems

All Solutions