Watch 10 video solutions for Rings and Rods, a easy level problem involving Hash Table, String. This walkthrough by Sandeep Kumar has 3,006 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 the rods. Every two characters in rings forms a color-position pair that is used to describe each ring where:
ith pair denotes the ith ring's color ('R', 'G', 'B').ith pair denotes the rod that the ith ring is placed on ('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.
Example 1:
Input: rings = "B0B6G0R6R0R6G9" Output: 1 Explanation: - 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 Explanation: - 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 Explanation: Only one ring is given. Thus, no rods have all three colors.
Constraints:
rings.length == 2 * n1 <= n <= 100rings[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).Problem Overview: You receive a string where every two characters represent a ring and the rod it is placed on. The first character is the ring color (R, G, B) and the second is a rod index from 0 to 9. The task is to count how many rods end up with all three colors.
Approach 1: Using Sets to Track Colors on Rods (Time: O(n), Space: O(1))
The straightforward solution maps each rod to the set of colors placed on it. Iterate through the string in steps of two characters. For each pair, extract the color and rod index, then insert the color into a set associated with that rod. Because rods are limited to digits 0-9, you can store these sets in a small array or hash map. After processing the entire string, check which rods have a set size of three, meaning they contain R, G, and B. This approach uses constant space because the number of rods never exceeds ten. It relies on fast membership tracking provided by a hash table style structure and straightforward iteration over the string.
Approach 2: Numeric Bitmask Representation (Time: O(n), Space: O(1))
A more compact approach encodes colors using bits instead of storing sets. Assign a bit to each color: R = 1, G = 2, B = 4. Maintain an integer array of size 10 where each index represents a rod. As you iterate through the string pairs, update the rod’s bitmask with a bitwise OR operation corresponding to the ring color. For example, adding a green ring sets the second bit. At the end, a rod containing all three colors will have the mask value 7 (1 | 2 | 4). Counting rods with value 7 gives the answer. This method eliminates set operations and replaces them with constant-time bitwise updates, making it both memory-efficient and fast in practice.
Recommended for interviews: Start with the set-based solution because it clearly models the problem: each rod stores the colors it has seen. The logic is easy to explain and implement quickly. After that, mention the bitmask optimization. Interviewers often like this improvement because it demonstrates comfort with space-efficient representations and bitwise reasoning while keeping the same O(n) runtime.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sets to track colors per rod | O(n) | O(1) | Best for readability and interviews when modeling the problem directly with collections |
| Numeric bitmask representation | O(n) | O(1) | When you want a compact representation and faster constant-time updates using bit operations |