Watch 8 video solutions for Count Residue Prefixes, a easy level problem involving Hash Table, String. This walkthrough by Programming Live with Larry has 146 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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. |