Is Count Residue Prefixes easy or hard?

Count Residue Prefixes is generally considered an easy problem because the solution relies on a standard prefix modulo pattern with a hash table. Once you recognize the residue frequency trick, the implementation becomes straightforward.

Count Residue Prefixes Python/Java solution

Implement the prefix residue technique with a hash map that tracks residue frequencies. Update the running residue while iterating through the string and accumulate matches whenever the same residue is encountered again.

How to solve Count Residue Prefixes in O(n)?

Maintain a running prefix value and compute its residue using modulo arithmetic. Store counts of residues in a hash map. Each time the same residue appears again, add the stored frequency to the result and update the map. This converts repeated prefix comparisons into constant‑time hash lookups.

What is the best approach for Count Residue Prefixes?

The most efficient approach uses a prefix residue calculation combined with a hash table. As you scan the string, compute the running modulo value and store frequencies of each residue. When the same residue appears again, previous prefixes contribute to the count. This produces an O(n) time solution.

Is Count Residue Prefixes asked at Google/Amazon/Meta?

Prefix sum and modulo hash table problems frequently appear in interviews at companies like Google, Amazon, and Meta. Variants of this pattern include subarray sum divisible by k and prefix remainder counting problems.

What data structure is used in Count Residue Prefixes?

A hash table (hash map) is the primary data structure. It stores how many times each residue value has appeared while scanning the string, allowing constant‑time frequency lookups.

What is the time complexity of Count Residue Prefixes?

The optimal solution runs in O(n) time because the string is scanned once and each residue lookup in the hash table is constant time on average. Space complexity is O(n) in the worst case to store residue frequencies.

Description Hints 1 Solution Video 3:09

3803. Count Residue Prefixes

Easy65.2% acceptance2 companies

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.

Example 1:

Input: s = "abc"

Output: 2

Explanation:

Prefix "a" has 1 distinct character and length modulo 3 is 1, so it is a residue.
Prefix "ab" has 2 distinct characters and length modulo 3 is 2, so it is a residue.
Prefix "abc" does not satisfy the condition. Thus, the answer is 2.

Example 2:

Input: s = "dd"

Output: 1

Explanation:

Prefix "d" has 1 distinct character and length modulo 3 is 1, so it is a residue.
Prefix "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:

Prefix "b" has 1 distinct character and length modulo 3 is 1, so it is a residue.
Prefix "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 <= 100
s contains only lowercase English letters.

Asked at 2 companies

Google Microsoft

Topics

Hash Table String

Hints open one at a time

Hint 1

Simulate as described

3:09

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def residuePrefixes(self, s: str) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

"abc"

Input

"dd"

Input

"bob"

Your code is saved on this device.Solution