3803. Count Residue Prefixes

EasyHash TableString

LeetCode ↗

Problem Pattern Idea Example Code Complex Pitfalls

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

For each prefix, we look at two values: the number of distinct characters it contains, and the remainder when its length is divided by 3. If these two values match, the prefix qualifies as a residue prefix. The task is to count how many such prefixes exist.

For example, consider a prefix of length 3. Since 3 % 3 = 0, this prefix would only be a residue if it contained 0 distinct characters — which is impossible for a non-empty prefix, so it can never qualify. For a prefix of length 1, since 1 % 3 = 1, it is a residue when it has exactly 1 distinct character, which is always true. For a prefix of length 2, since 2 % 3 = 2, it is a residue only when both characters are different, giving 2 distinct characters.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why Simulation / Basic DSA?

This problem maps to Simulation / Basic DSA through a short path in the full flowchart.

Counting prefixes where the number of distinct characters equals length % 3 is a simple incremental scan with a set to track distinct characters.

Open in Flowchart

Intuition

The key observation is that prefixes have a natural nested structure: the prefix of length i is simply the prefix of length i - 1 with one more character appended. This means we don't need to recompute everything from scratch for each prefix — we can build up our information incrementally as we scan the string from left to right.

The only piece of information we need to track for each prefix is the number of distinct characters it contains. As we move from one character to the next, we just add the new character to a running collection of seen characters. A natural choice for this collection is a hash set, because it automatically ignores duplicates, so its size always tells us exactly how many distinct characters we have seen so far.

Once we have the distinct-character count for the current prefix, the rest is straightforward. The length of the current prefix is just its position index (counting from 1), so we compute len(prefix) % 3 and compare it with the size of the hash set. Whenever the two values are equal, the current prefix is a residue prefix, and we add 1 to our answer.

Because we process each character exactly once and only do constant-time work per character, this approach naturally arrives at an efficient single-pass solution.

Solution Approach

Solution 1: Hash Table

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.

Let's break down the implementation step by step:

Initialize an empty hash set st to keep track of the distinct characters seen so far, and a counter ans set to 0 to record the number of residue prefixes.
Iterate over the string s using enumerate(s, 1), so that the index i starts from 1. This index i directly represents the length of the current prefix.
For each character c, add it to the set st. After this, the size of st (i.e., len(st)) equals the number of distinct characters in the prefix of length i.
Check whether len(st) == i % 3. If this condition holds, the current prefix is a residue prefix, so we increment ans by 1.
After the iteration finishes, return ans as the final answer.

The time complexity is O(n), where n is the length of the string s, since we process each character exactly once and each set operation takes constant time on average. The space complexity is O(|\Sigma|), where |\Sigma| is the size of the character set. Since s consists only of lowercase English letters, the set can hold at most 26 distinct characters, so the space used is constant.

Example Walkthrough

Let's walk through the solution using the small example s = "aba".

We maintain a hash set st to track distinct characters seen so far, and a counter ans initialized to 0. We iterate with index i starting from 1, where i represents the current prefix length.

Step 1: i = 1, c = 'a'

Add 'a' to st, so st = {'a'} and len(st) = 1.
Compute i % 3 = 1 % 3 = 1.
Compare: len(st) == i % 3 → 1 == 1 ✓
The prefix "a" is a residue prefix. Increment ans to 1.

Step 2: i = 2, c = 'b'

Add 'b' to st, so st = {'a', 'b'} and len(st) = 2.
Compute i % 3 = 2 % 3 = 2.
Compare: len(st) == i % 3 → 2 == 2 ✓
The prefix "ab" is a residue prefix. Increment ans to 2.

Step 3: i = 3, c = 'a'

Add 'a' to st, but it already exists, so st = {'a', 'b'} and len(st) = 2.
Compute i % 3 = 3 % 3 = 0.
Compare: len(st) == i % 3 → 2 == 0 ✗
The prefix "aba" is not a residue prefix. ans stays at 2.

Result: After processing all characters, we return ans = 2.

This matches our intuition: the prefixes "a" (length 1, 1 distinct char) and "ab" (length 2, 2 distinct chars) qualify, while "aba" (length 3, requiring 0 distinct chars) cannot. Notice how the set was built incrementally — we never recomputed distinct counts from scratch, and the duplicate 'a' in Step 3 was automatically ignored by the set.

Solution Implementation

1class Solution:
2    def residuePrefixes(self, s: str) -> int:
3        # Set to track the distinct characters seen so far in the prefix
4        distinct_chars: set[str] = set()
5        # Counter for the number of qualifying prefixes
6        count = 0
7
8        # Iterate over the string; `length` is the 1-based length of the current prefix
9        for length, char in enumerate(s, start=1):
10            # Add the current character to the set of distinct characters
11            distinct_chars.add(char)
12
13            # Check if the number of distinct characters equals the prefix length modulo 3
14            if len(distinct_chars) == length % 3:
15                count += 1
16
17        return count
18

1class Solution {
2    public int residuePrefixes(String s) {
3        // Set to track distinct characters seen in the current prefix
4        Set<Character> distinctChars = new HashSet<>();
5
6        // Counter for prefixes that satisfy the condition
7        int count = 0;
8
9        // Iterate over each prefix of length i (1-based)
10        for (int i = 1; i <= s.length(); i++) {
11            // Current character at position (i - 1) in 0-based indexing
12            char currentChar = s.charAt(i - 1);
13
14            // Add the character to the set of distinct characters
15            distinctChars.add(currentChar);
16
17            // Check if the number of distinct characters equals (i mod 3)
18            if (distinctChars.size() == i % 3) {
19                count++;
20            }
21        }
22
23        return count;
24    }
25}
26

1class Solution {
2public:
3    int residuePrefixes(string s) {
4        // Tracks the set of distinct characters seen so far in the prefix.
5        unordered_set<char> distinctChars;
6
7        // Counts how many prefixes satisfy the condition.
8        int count = 0;
9
10        // Iterate over each prefix of length `length` (1-based).
11        for (int length = 1; length <= static_cast<int>(s.size()); ++length) {
12            // The character at the current end of the prefix (0-based index).
13            char currentChar = s[length - 1];
14
15            // Add it to the set of distinct characters.
16            distinctChars.insert(currentChar);
17
18            // Check whether the number of distinct characters equals
19            // the prefix length modulo 3.
20            if (static_cast<int>(distinctChars.size()) == length % 3) {
21                ++count;
22            }
23        }
24
25        return count;
26    }
27};
28

1/**
2 * Counts the number of prefixes whose count of distinct characters
3 * equals the prefix length taken modulo 3.
4 *
5 * For each prefix s[0..i], we track the set of distinct characters.
6 * The prefix length is (i + 1). If the number of distinct characters
7 * equals (i + 1) % 3, the prefix qualifies and is counted.
8 *
9 * @param s - The input string to scan.
10 * @returns The number of qualifying prefixes.
11 */
12function residuePrefixes(s: string): number {
13    // Holds the distinct characters encountered so far.
14    const distinctChars = new Set<string>();
15
16    // Accumulates the count of qualifying prefixes.
17    let count = 0;
18
19    for (let i = 0; i < s.length; i++) {
20        // Current character of the prefix ending at index i.
21        const currentChar = s[i];
22
23        // Add the character; duplicates are ignored by the Set.
24        distinctChars.add(currentChar);
25
26        // Current prefix length is (i + 1); compare its residue mod 3
27        // against the number of distinct characters in the prefix.
28        const prefixLengthResidue = (i + 1) % 3;
29
30        if (distinctChars.size === prefixLengthResidue) {
31            count++;
32        }
33    }
34
35    return count;
36}
37

Time and Space Complexity

Time Complexity: O(n), where n is the length of the string s. The code iterates through the string with a single loop. For each character, the operations performed—adding the character to the set (st.add(c)), computing the set's length (len(st)), and the modulo comparison (i % 3)—all take O(1) time on average. Therefore, the total time complexity is O(n).
Space Complexity: O(n), where n is the length of the string s. The set st is used to store distinct characters encountered while traversing the string. In the worst case, when all characters in s are unique, the set may hold up to n characters, resulting in O(n) space usage.

Pattern Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Confusing "distinct characters in the prefix" with "total length of the prefix"

A very common mistake is to compare the prefix length itself against length % 3, instead of comparing the number of distinct characters against length % 3. These are two completely different quantities.

For example, for the prefix "aab" (length 3):

The number of distinct characters is 2 (a and b).
The prefix length is 3, and 3 % 3 = 0.

The correct check compares distinct count (2) against length % 3 (0), which does not match. But if you mistakenly write if length == length % 3, you would get an entirely wrong comparison.

Incorrect:

for length, char in enumerate(s, start=1):
    distinct_chars.add(char)
    if length == length % 3:   # WRONG: compares length with itself mod 3
        count += 1

Correct:

for length, char in enumerate(s, start=1):
    distinct_chars.add(char)
    if len(distinct_chars) == length % 3:   # compares distinct count vs length mod 3
        count += 1

The key is to always use len(distinct_chars), not length, on the left side of the comparison.

Pitfall 2: Off-by-one error from 0-based indexing

The problem defines the prefix length as starting from 1 (a non-empty prefix of one character has length 1). If you iterate with the default enumerate(s) (which starts the index at 0), then your "length" value is actually index + 1, and forgetting this leads to an off-by-one error in the modulo calculation.

Incorrect:

for i, char in enumerate(s):       # i starts at 0
    distinct_chars.add(char)
    if len(distinct_chars) == i % 3:   # WRONG: i is index, not length
        count += 1

Here, when processing the first character, i = 0, so i % 3 = 0, but len(distinct_chars) = 1. The condition fails even though a length-1 prefix should always qualify (1 % 3 = 1 and distinct count is 1).

Correct:

for i, char in enumerate(s):
    distinct_chars.add(char)
    length = i + 1                      # convert to 1-based length
    if len(distinct_chars) == length % 3:
        count += 1

Or simply use enumerate(s, start=1) as in the original solution so that the loop variable directly represents the prefix length.

Pitfall 3: Resetting or misusing the distinct-character set

The set distinct_chars must accumulate characters across the entire iteration, because each prefix builds on the previous one. A mistake is to reset the set inside the loop or to recompute distinct characters from scratch for every prefix (which is correct but inefficient, turning an O(n) solution into O(n²)).

Incorrect (resets the set each iteration):

for length, char in enumerate(s, start=1):
    distinct_chars = set()   # WRONG: loses all previously seen characters
    distinct_chars.add(char)
    if len(distinct_chars) == length % 3:
        count += 1

Inefficient (recomputes from scratch, O(n²)):

for length in range(1, len(s) + 1):
    distinct_count = len(set(s[:length]))   # rebuilds the set every time
    if distinct_count == length % 3:
        count += 1

Correct (incrementally grow the set): keep the set declared once before the loop and only add to it, so it always reflects the distinct characters of the current prefix in O(1) per step.

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap:

Core Learning

LLD/OOP Interview

Additional Resources

AI Engineering