3803. Count Residue Prefixes - Solution & Explanation

Q: Is Count Residue Prefixes easy or hard?

Count Residue Prefixes is generally considered an easy problem because the solution relies on a standard prefix modulo pattern with a hash table. Once you recognize the residue frequency trick, the implementation becomes straightforward.

Q: Count Residue Prefixes Python/Java solution

Implement the prefix residue technique with a hash map that tracks residue frequencies. Update the running residue while iterating through the string and accumulate matches whenever the same residue is encountered again.

Q: How to solve Count Residue Prefixes in O(n)?

Maintain a running prefix value and compute its residue using modulo arithmetic. Store counts of residues in a hash map. Each time the same residue appears again, add the stored frequency to the result and update the map. This converts repeated prefix comparisons into constant‑time hash lookups.

Q: What is the best approach for Count Residue Prefixes?

The most efficient approach uses a prefix residue calculation combined with a hash table. As you scan the string, compute the running modulo value and store frequencies of each residue. When the same residue appears again, previous prefixes contribute to the count. This produces an O(n) time solution.

Q: Is Count Residue Prefixes asked at Google/Amazon/Meta?

Prefix sum and modulo hash table problems frequently appear in interviews at companies like Google, Amazon, and Meta. Variants of this pattern include subarray sum divisible by k and prefix remainder counting problems.

Q: What data structure is used in Count Residue Prefixes?

A hash table (hash map) is the primary data structure. It stores how many times each residue value has appeared while scanning the string, allowing constant‑time frequency lookups.

Q: What is the time complexity of Count Residue Prefixes?

The optimal solution runs in O(n) time because the string is scanned once and each residue lookup in the hash table is constant time on average. Space complexity is O(n) in the worst case to store residue frequencies.

The problem

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.

Approach overview

Problem Overview: You are given a string and need to count how many prefixes produce the same residue when evaluated under a modulo rule. The goal is to process prefixes efficiently instead of recomputing values for every substring.

Approach 1: Brute Force Prefix Evaluation (O(n²) time, O(1) space)

Generate every prefix of the string and compute its residue directly. For each prefix, iterate through its characters, convert each character to a numeric value (for example ord(c) based mapping), maintain a running sum, and compute sum % k. If the residue matches the required condition, increment the result. This approach is straightforward but repeatedly recomputes prefix values, which leads to quadratic work for long strings.

Approach 2: Prefix Residue + Hash Table (O(n) time, O(n) space)

Track the running residue while scanning the string once. For every character, update a prefix value and compute its residue using prefix = (prefix + value) % k. A hash table stores how many times each residue has appeared so far. If the current residue has been seen before, those earlier prefixes form valid matches. Add the stored frequency to the answer and update the hash map. This avoids recomputing prefix values and converts the solution into a single pass.

The key insight: two prefixes with the same residue imply their difference cancels out modulo k. Hash lookups make residue frequency tracking constant time.

This pattern appears frequently with prefix computations on arrays and strings, especially when using modular arithmetic. You iterate through the string, update the running prefix value, and store residue frequencies in a hash table.

Recommended for interviews: The hash table prefix-residue approach. Interviewers expect you to recognize the prefix modulo pattern and convert repeated residue checks into constant‑time hash lookups. Explaining the brute force method first shows you understand the baseline, but the O(n) prefix + hash table solution demonstrates algorithmic optimization.

Solution

We use a hash table 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 st, and then check if the length of the current prefix modulo 3 equals the size of the set 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.

Python

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

Java

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

C++

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

TypeScript

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

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
}

Try this approach in the editor

Complexity analysis

Approach	Time	Space	When to Use
Brute Force Prefix Evaluation	O(n²)	O(1)	Useful for understanding the problem or when the string is very small.
Prefix Residue with Hash Table	O(n)	O(n)	General case. Efficient for large strings where prefix residues must be tracked quickly.

Frequently asked questions

Is Count Residue Prefixes easy or hard?

Count Residue Prefixes is generally considered an easy problem because the solution relies on a standard prefix modulo pattern with a hash table. Once you recognize the residue frequency trick, the implementation becomes straightforward.

Count Residue Prefixes Python/Java solution

Implement the prefix residue technique with a hash map that tracks residue frequencies. Update the running residue while iterating through the string and accumulate matches whenever the same residue is encountered again.

How to solve Count Residue Prefixes in O(n)?

Maintain a running prefix value and compute its residue using modulo arithmetic. Store counts of residues in a hash map. Each time the same residue appears again, add the stored frequency to the result and update the map. This converts repeated prefix comparisons into constant‑time hash lookups.

What is the best approach for Count Residue Prefixes?

The most efficient approach uses a prefix residue calculation combined with a hash table. As you scan the string, compute the running modulo value and store frequencies of each residue. When the same residue appears again, previous prefixes contribute to the count. This produces an O(n) time solution.

Is Count Residue Prefixes asked at Google/Amazon/Meta?

Prefix sum and modulo hash table problems frequently appear in interviews at companies like Google, Amazon, and Meta. Variants of this pattern include subarray sum divisible by k and prefix remainder counting problems.

What data structure is used in Count Residue Prefixes?

A hash table (hash map) is the primary data structure. It stores how many times each residue value has appeared while scanning the string, allowing constant‑time frequency lookups.

What is the time complexity of Count Residue Prefixes?

The optimal solution runs in O(n) time because the string is scanned once and each residue lookup in the hash table is constant time on average. Space complexity is O(n) in the worst case to store residue frequencies.

Count Residue Prefixes solution and explanation

The problem

Approach overview

Solution

Complexity analysis

Frequently asked questions

Comments

Count Residue Prefixes solution and explanation

The problem

Approach overview

Solution

Complexity analysis

Frequently asked questions

Comments

Related problems