LeetCode 3803 - Count Residue Prefixes

LeetCode Problem 3803

Difficulty: 🟢 Easy
Topics: Hash Table, String

Solution

Problem Understanding

The problem asks us to analyze prefixes of a string s and count how many of them satisfy a specific condition. A prefix is any substring that starts at the first character and extends to some point in the string. For a prefix to be a residue, the number of distinct characters in that prefix must equal len(prefix) % 3, where len(prefix) is the length of the prefix.

The input s is a string of lowercase English letters with length ranging from 1 to 100. The output is a single integer representing the count of residue prefixes.

Key observations are that the modulo operation limits the number of distinct characters needed for a prefix to be a residue, and that prefixes grow incrementally, so we can compute distinct character counts efficiently. Important edge cases include strings where all characters are the same, strings where all characters are unique, and strings of length 1.

Approaches

A brute-force approach would generate every prefix of the string, count the number of distinct characters in each, compute the length modulo 3, and compare. This works because it directly follows the problem definition, but it is inefficient since counting distinct characters repeatedly for overlapping prefixes is redundant.

The optimal approach leverages the incremental nature of prefixes. We maintain a hash set of characters seen so far and update it as we extend the prefix. This way, counting distinct characters at each step is constant time, and we only compute modulo and comparison for each prefix once. Given the constraints (s.length <= 100), this is efficient.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n^2)	O(n)	Generates all prefixes, counts distinct characters for each
Optimal	O(n)	O(1)	Maintains a set of distinct characters incrementally

Algorithm Walkthrough

1. Initialize an empty set seen to store distinct characters encountered so far.
2. Initialize a counter count to zero to track the number of residue prefixes.
3. Iterate over the string with index i ranging from 0 to len(s) - 1.
4. Add the current character s[i] to the seen set.
5. Compute the number of distinct characters in the prefix as len(seen).
6. Compute the length of the current prefix modulo 3 as (i + 1) % 3.
7. If the number of distinct characters equals the modulo result, increment count.
8. After iterating through the string, return count.

Why it works: The set seen accumulates all unique characters in the prefix incrementally. Each prefix is processed in order, and the condition is checked exactly once per prefix. This guarantees correct counting without redundant calculations.

Python Solution

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

The Python implementation directly follows the algorithm. The set seen ensures uniqueness of characters, enumerate provides both the index and character, and (i + 1) % 3 calculates the length modulo efficiently. The conditional increments the count only when the residue condition is satisfied.

Go Solution

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

The Go implementation mirrors Python. A map[rune]struct{} is used instead of a set since Go does not have a built-in set type. Each character is added to the map with an empty struct as value. The logic for counting residue prefixes remains identical.

Worked Examples

Example 1: s = "abc"

i	Prefix	Seen	Distinct	Length % 3	Residue?	Count
0	"a"	{a}	1	1	Yes	1
1	"ab"	{a,b}	2	2	Yes	2
2	"abc"	{a,b,c}	3	0	No	2

Example 2: s = "dd"

i	Prefix	Seen	Distinct	Length % 3	Residue?	Count
0	"d"	{d}	1	1	Yes	1
1	"dd"	{d}	1	2	No	1

Example 3: s = "bob"

i	Prefix	Seen	Distinct	Length % 3	Residue?	Count
0	"b"	{b}	1	1	Yes	1
1	"bo"	{b,o}	2	2	Yes	2
2	"bob"	{b,o}	2	0	No	2

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each character is processed exactly once, and set operations are O(1) on average
Space	O(1)	The set can hold at most 26 characters (lowercase letters), constant relative to input size

Given the input constraint of at most 100 characters, this approach is efficient and memory usage is minimal.

Test Cases

# Provided examples
assert Solution().residuePrefixes("abc") == 2  # multiple distinct characters
assert Solution().residuePrefixes("dd") == 1   # repeated character
assert Solution().residuePrefixes("bob") == 2  # mix of repeated and unique

# Boundary cases
assert Solution().residuePrefixes("a") == 1    # single character
assert Solution().residuePrefixes("aaa") == 1  # all same character
assert Solution().residuePrefixes("abcdefghijklmnopqrstuvwxyz") == 0  # all unique, length modulo mismatches

# Stress cases
assert Solution().residuePrefixes("abababababab") == 4  # repeating pattern
assert Solution().residuePrefixes("abcabcabcabc") == 6  # repeating pattern with distinct growth

Test	Why
"abc"	Checks standard case with increasing distinct characters
"dd"	Checks repeated characters with modulo mismatch
"bob"	Checks alternating repeated and new characters
"a"	Minimal input
"aaa"	Repeated single character
"abcdefghijklmnopqrstuvwxyz"	Max distinct characters scenario
"abababababab"	Pattern repetition
"abcabcabcabc"	Repeating pattern with growth of distinct characters

Edge Cases

A key edge case is a string of length 1. Since 1 % 3 = 1, any single character string is always a residue prefix. The implementation correctly handles this because the first iteration will always satisfy len(seen) == (i+1)%3.

Another important edge case is when all characters are the same. For example, "aaaa". Here, only the first prefix can satisfy the residue condition since all subsequent prefixes have length modulo increasing while the number of distinct characters remains 1. The algorithm handles this because the set seen will not grow further, ensuring correct comparison at each step.

A third edge case is when all characters are distinct, such as "abcdef". Eventually, the number of distinct characters may exceed the modulo length, causing no further residues. The incremental checking with the set ensures that the correct residue prefixes are counted before this point, avoiding overcounting.