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.
Example 1:
Input: s = "abc"
Output: 2
Explanation:
"a" has 1 distinct character and length modulo 3 is 1, so it is a residue."ab" has 2 distinct characters and length modulo 3 is 2, so it is a residue."abc" does not satisfy the condition. Thus, the answer is 2.Example 2:
Input: s = "dd"
Output: 1
Explanation:
"d" has 1 distinct character and length modulo 3 is 1, so it is a residue."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:
"b" has 1 distinct character and length modulo 3 is 1, so it is a residue."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 <= 100s contains only lowercase English letters.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.
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
Java
C++
Go
TypeScript
| 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. |
3803. Count Residue Prefixes (Leetcode Easy) • Programming Live with Larry • 146 views views
Watch 7 more video solutions →Practice Count Residue Prefixes with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor