Rings and Rods

Difficulty: Easy | Acceptance: 81.50% | Paid: No Topics: Hash Table, String

There are n rings and each ring is either red, green, or blue. The rings are distributed across ten rods labeled from 0 to 9.

You are given a string rings of length 2n that describes the n rings that are placed onto rods. Every two characters in rings forms a color-position pair that describes a ring where:

The first character of the ith pair denotes the ith ring’s color (‘R’, ‘G’, ‘B’). The second character of the ith pair denotes the rod that the ith ring is placed onto (‘0’ to ‘9’).

For example, “R3G2B1” describes n == 3 rings: a red ring placed onto the rod labeled 3, a green ring placed onto the rod labeled 2, and a blue ring placed onto the rod labeled 1.

Return the number of rods that have all three colors of rings on them.

• Examples
• Constraints
• Hash Map Approach
• Bitmask Approach
• Array of Sets Approach

Examples

Input: rings = "B0B6G0R6R0R6G9"
Output: 1
Explanation: 
- Rod 0 has 3 rings: red, green, blue.
- Rod 6 has 3 rings: red, red, red.
- Rod 9 has 1 ring: green.
Only rod 0 has all three colors.

Input: rings = "B0R0G0R9R0B0G0"
Output: 2
Explanation: 
- Rod 0 has 6 rings: red, green, blue, red, blue, green.
- Rod 9 has 1 ring: red.
Rods 0 and 9 have all three colors.

Input: rings = "G4"
Output: 0
Explanation: 
Only one ring is placed. Only rod 4 has a ring and it is green.
No rod has all three colors.

Constraints

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

Hash Map Approach

Intuition Use a hash map to track which colors are on each rod, then count rods with all three colors.

Steps

• Create a hash map where keys are rod identifiers and values are sets of colors
• Iterate through the string in pairs (color, rod)
• Add each color to the corresponding rod’s color set
• Count rods whose color set has size 3

class Solution:
    def countPoints(self, rings: str) -> int:
        rods = {}
        for i in range(0, len(rings), 2):
            color = rings[i]
            rod = rings[i+1]
            if rod not in rods:
                rods[rod] = set()
            rods[rod].add(color)
        count = 0
        for rod in rods:
            if len(rods[rod]) == 3:
                count += 1
        return count

Complexity

• Time: O(n) where n is the length of the string
• Space: O(1) since we have at most 10 rods and 3 colors
• Notes: Clean and readable approach using hash map with sets

Bitmask Approach

Intuition Represent each rod’s colors using a 3-bit integer where each bit corresponds to a color (R=1, G=2, B=4).

Steps

• Create an array of 10 integers initialized to 0
• Map each color to a power of 2: R→1, G→2, B→4
• For each ring, OR the corresponding bit into the rod’s mask
• Count rods where mask equals 7 (all three bits set)

class Solution:
    def countPoints(self, rings: str) -> int:
        rods = [0] * 10
        color_map = {'R': 1, 'G': 2, 'B': 4}
        for i in range(0, len(rings), 2):
            color = rings[i]
            rod = int(rings[i+1])
            rods[rod] |= color_map[color]
        count = 0
        for mask in rods:
            if mask == 7:
                count += 1
        return count

Complexity

• Time: O(n) where n is the length of the string
• Space: O(1) fixed array of 10 integers
• Notes: Most space-efficient approach using bitwise operations

Array of Sets Approach

Intuition Since rods are numbered 0-9, use direct array indexing with sets for color tracking.

Steps

• Create an array of 10 empty sets
• Iterate through the string in pairs
• Convert rod character to integer index
• Add color to the corresponding set
• Count sets with size 3

class Solution:
    def countPoints(self, rings: str) -> int:
        rods = [set() for _ in range(10)]
        for i in range(0, len(rings), 2):
            color = rings[i]
            rod = int(rings[i+1])
            rods[rod].add(color)
        count = 0
        for colors in rods:
            if len(colors) == 3:
                count += 1
        return count

Complexity

• Time: O(n) where n is the length of the string
• Space: O(1) fixed array of 10 sets
• Notes: Simple and intuitive with direct array access