Mutating counts without cleanup
Wrong move: Zero-count keys stay in map and break distinct/count constraints.
Usually fails on: Window/map size checks are consistently off by one.
Fix: Delete keys when count reaches zero.
Build confidence with an intuition-first walkthrough focused on hash map fundamentals.
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 summary: 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.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Hash Map
"abc"
"dd"
"bob"
Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #3803: Count Residue Prefixes
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;
}
}
// Accepted solution for LeetCode #3803: Count Residue Prefixes
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
}
# Accepted solution for LeetCode #3803: Count Residue Prefixes
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
// Accepted solution for LeetCode #3803: Count Residue Prefixes
fn residue_prefixes(s: String) -> i32 {
use std::collections::HashSet;
let mut checked = HashSet::new();
let mut ret = 0;
for (i, c) in s.chars().enumerate() {
checked.insert(c);
if (i + 1) % 3 == checked.len() {
ret += 1;
}
}
ret
}
fn main() {
let ret = residue_prefixes("abc".to_string());
println!("ret={ret}");
}
#[test]
fn test() {
assert_eq!(residue_prefixes("abc".to_string()), 2);
assert_eq!(residue_prefixes("dd".to_string()), 1);
assert_eq!(residue_prefixes("bob".to_string()), 2);
assert_eq!(residue_prefixes("a".to_string()), 1);
assert_eq!(residue_prefixes("bbbb".to_string()), 2);
}
// Accepted solution for LeetCode #3803: Count Residue Prefixes
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;
}
Use this to step through a reusable interview workflow for this problem.
For each element, scan the rest of the array looking for a match. Two nested loops give n × (n−1)/2 comparisons = O(n²). No extra space since we only use loop indices.
One pass through the input, performing O(1) hash map lookups and insertions at each step. The hash map may store up to n entries in the worst case. This is the classic space-for-time tradeoff: O(n) extra memory eliminates an inner loop.
Review these before coding to avoid predictable interview regressions.
Wrong move: Zero-count keys stay in map and break distinct/count constraints.
Usually fails on: Window/map size checks are consistently off by one.
Fix: Delete keys when count reaches zero.