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.
In this approach, we use an array of sets to maintain a list of colors present on each rod. As we parse the input, we add the color of each ring to the corresponding set for its rod. Finally, we count the number of sets that contain all three colors.
This solution utilizes a 2D boolean array where each row represents a rod and each column represents a color (0 for R, 1 for G, 2 for B). As we iterate through the ring string, we update the respective rod's color status. At the end, we count rods with all color statuses set to true.
Time Complexity: O(n), where n is the number of rings. Each ring is processed in constant time.
Space Complexity: O(1), as the size of the rods array is constant (10x3).
In this approach, each rod is represented by a bitmask of three bits indicating the presence of the colors R, G, and B. We iterate through the string to update each rod's bitmask and finally count rods with a bitmask value of 7 (binary 111, meaning all colors are present).
This C solution uses an integer array where each element stores bitmask values corresponding to the colors on each rod. Each rod's bitmask is composed as rings are processed, and a rod counts if its mask equals 7 (0b111).
Time Complexity: O(n), as each ring is processed in constant time.
Space Complexity: O(1), given the fixed number of rods (10).
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 ith rod. If there are red, green, and blue rings on the ith rod, then the binary representation of mask[i] is 111, that is, mask[i] = 7.
We traverse the string rings. For each color position pair (c, j), where c represents the color of the ring and j represents the number of the rod where the ring is located, we set the corresponding binary bit of mask[j], that is, mask[j] |= d[c], where d[c] represents the binary bit corresponding to color c.
Finally, we count the number of elements in mask that are 7, which is the number of rods that have collected all three colors of rings.
The time complexity is O(n), and the space complexity is O(|\Sigma|), where n represents the length of the string rings, and |\Sigma| represents the size of the character set.
TypeScript
| Approach | Complexity |
|---|---|
| Approach 1: Using Sets to Track Colors on Rods | Time Complexity: O(n), where n is the number of rings. Each ring is processed in constant time. |
| Approach 2: Numeric Bitmask Representation | Time Complexity: O(n), as each ring is processed in constant time. |
| Bit Manipulation | — |
| Default Approach | — |
| 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 |
Leetcode 2103 - Rings and Rods - Video Editorial • Sandeep Kumar • 3,006 views views
Watch 9 more video solutions →Practice Rings and Rods with our built-in code editor and test cases.
Practice on FleetCode