#2103

Easy

LeetCode Problem Workspace

Rings and Rods

Count how many rods have all three colors using a hash table to track colors per rod efficiently in strings.

Problem Statement

You are given a string representing n rings placed on ten rods labeled from 0 to 9. Each ring is either red, green, or blue, and the string consists of pairs where the first character is the color and the second character is the rod number. For example, 'R3G2B1' describes a red ring on rod 3, a green ring on rod 2, and a blue ring on rod 1.

Your task is to count how many rods contain at least one ring of each color. Work through the string, track colors per rod, and return the total number of rods that have red, green, and blue rings. Optimize using a hash table to store rod-color associations efficiently.

Examples

Example 1

Input: rings = "B0B6G0R6R0R6G9"

Output: 1

The rod labeled 0 holds 3 rings with all colors: red, green, and blue.
The rod labeled 6 holds 3 rings, but it only has red and blue.
The rod labeled 9 holds only a green ring. Thus, the number of rods with all three colors is 1.

Example 2

Input: rings = "B0R0G0R9R0B0G0"

Output: 1

The rod labeled 0 holds 6 rings with all colors: red, green, and blue.
The rod labeled 9 holds only a red ring. Thus, the number of rods with all three colors is 1.

Example 3

Input: rings = "G4"

Output: 0

Only one ring is given. Thus, no rods have all three colors.

Constraints

rings.length == 2 * n
1 <= n <= 100
rings[i] where i is even is either 'R', 'G', or 'B' (0-indexed).
rings[i] where i is odd is a digit from '0' to '9' (0-indexed).

Solution Approach

Map rods to color sets

Initialize a hash table where keys are rod numbers and values are sets of colors. Iterate over the string in pairs, adding each color to the corresponding rod's set. This efficiently tracks all colors per rod while handling repeated rings.

Count rods with all colors

After building the rod-color mapping, iterate through all rods and count how many sets contain all three colors: red, green, and blue. This step directly identifies rods meeting the requirement without extra iterations over the string.

Optimize for string traversal

Process the string in a single pass by extracting color and rod pairs and updating the hash table immediately. Avoid nested loops over rods or colors to maintain linear time complexity proportional to the number of rings.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) where n is the number of rings, since each pair is processed once. Space complexity is O(1) because there are at most 10 rods and 3 colors, so the hash table size is constant.

What Interviewers Usually Probe

Tracking colors per rod efficiently using a hash table.
Iterating over string pairs correctly without skipping or overlapping indices.
Counting rods with all colors correctly after mapping.

Common Pitfalls or Variants

Common pitfalls

Misinterpreting color-position pairs and swapping indices.
Forgetting to check all three colors when counting rods.
Using nested loops unnecessarily and increasing time complexity.

Follow-up variants

Count rods that contain exactly two colors instead of all three.
Allow rods to have multiple rings of the same color and count distinct color occurrences.
Extend rods from 10 to m rods with dynamic labeling, adjusting the hash table accordingly.

FAQ

What pattern does the Rings and Rods problem primarily use?

It uses a Hash Table plus String pattern, mapping each rod to a set of colors.

How do I efficiently track multiple colors per rod?

Use a hash table with rod numbers as keys and sets of colors as values for constant-time updates.

Can rods have repeated colors in the input string?

Yes, but only distinct colors per rod matter when counting rods with all three colors.

What is the optimal time complexity for this problem?

The optimal time complexity is O(n), where n is the number of rings, since each color-position pair is processed once.

How does GhostInterview verify the solution?

It tracks the color sets per rod and confirms which rods contain all three colors, highlighting mistakes immediately.

terminal

Solution

Solution 1: Bit Manipulation

We can use an array $mask$ of length $10$ to represent the color situation of the rings on each rod, where $mask[i]$ represents the color situation of the ring on the $i$th rod. If there are red, green, and blue rings on the $i$th rod, then the binary representation of $mask[i]$ is $111$, that is, $mask[i] = 7$.

1

2

3

4

5

6

7

8

9

class Solution:
    def countPoints(self, rings: str) -> int:
        mask = [0] * 10
        d = {"R": 1, "G": 2, "B": 4}
        for i in range(0, len(rings), 2):
            c = rings[i]
            j = int(rings[i + 1])
            mask[j] |= d[c]
        return mask.count(7)

Solution 2

#### TypeScript

1

2

3

4

5

6

7

8

9

class Solution:
    def countPoints(self, rings: str) -> int:
        mask = [0] * 10
        d = {"R": 1, "G": 2, "B": 4}
        for i in range(0, len(rings), 2):
            c = rings[i]
            j = int(rings[i + 1])
            mask[j] |= d[c]
        return mask.count(7)

Continue Practicing

#2115 find all possible recipes from given supplies #2085 count common words with one occurrence #2131 longest palindrome by concatenating two letter words