# Rings and Rods
**Difficulty:** EASY
[External](https://leetcode.com/problems/rings-and-rods)
Canonical: https://scaleengineer.com/dsa/problems/rings-and-rods
**Data structures:** Hash Table, String
---
## Problem
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:

* 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 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:**

![](https://assets.glich.co/dsa/rings-and-rods/image0.png) 

**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:**

![](https://assets.glich.co/dsa/rings-and-rods/image1.png) 

**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 * 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**).

# Approaches
## Using a Hash Map and Sets
This approach uses a Hash Map to store the information about which colors are present on each rod. The keys of the map are the rod indices (0-9), and the values are Sets of characters representing the colors ('R', 'G', 'B'). Using a Set for colors automatically handles duplicate colors on the same rod, simplifying the logic.
**Time:** O(N), where N is the length of the `rings` string. We iterate through the string once. Map and set operations (put, get, add) take average O(1) time. The final loop runs at most 10 times, which is a constant factor. · **Space:** O(1) - Constant space. Since there are at most 10 rods and 3 colors, the space required for the map and sets is bounded by a constant (10 keys, each with a set of at most 3 characters).
**Pros:** The logic is straightforward and easy to understand as it directly models the problem's entities.; It's flexible and would work even if the rod indices were not sequential or small integers.
**Cons:** Has slightly more overhead compared to using arrays due to the nature of hash maps (e.g., calculating hash codes, handling collisions).; Requires using wrapper classes (`Integer`) and `HashSet` objects, which can be less memory-efficient than primitive arrays.
### Explanation
The core idea is to model the problem directly using data structures that fit the description. A map is a natural choice to associate rods (keys) with their properties (values). Since each rod can have multiple rings of different colors, a set is used as the value to store the unique colors found on that rod.

1.  Initialize a `HashMap<Integer, Set<Character>>`.
2.  Iterate through the input string `rings` by pairs of characters. For each pair, the first character is the color and the second is the rod index.
3.  Parse the rod index and the color. For each rod, find its corresponding set in the map. If the rod is encountered for the first time, create a new `HashSet` for it.
4.  Add the current color to the rod's set. The set will only store unique colors.
5.  After processing all the rings, iterate through the values of the map (which are the sets of colors).
6.  Count how many of these sets have a size of 3. A size of 3 indicates that the rod contains rings of all three distinct colors (Red, Green, and Blue).
7.  This count is the final answer.

```java
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

class Solution {
    public int countPoints(String rings) {
        Map<Integer, Set<Character>> rods = new HashMap<>();
        
        for (int i = 0; i < rings.length(); i += 2) {
            char color = rings.charAt(i);
            int rodIndex = rings.charAt(i + 1) - '0';
            
            // Get the set of colors for the current rod, or create a new one
            rods.putIfAbsent(rodIndex, new HashSet<>());
            
            // Add the color to the set for that rod
            rods.get(rodIndex).add(color);
        }
        
        int count = 0;
        // Iterate through the map's values (the sets of colors)
        for (Set<Character> colors : rods.values()) {
            // If a set has 3 colors, it means the rod has all three
            if (colors.size() == 3) {
                count++;
            }
        }
        
        return count;
    }
}
```
### Algorithm
- Create a `HashMap<Integer, Set<Character>>` named `rods` to map rod indices to the set of colors on them.
- Loop through the `rings` string with a step of 2.
- In each iteration, extract the `color` character and the `rodIndex` integer.
- Use `rods.putIfAbsent(rodIndex, new HashSet<>())` to ensure a set exists for the current rod.
- Add the `color` to the set for the `rodIndex` using `rods.get(rodIndex).add(color)`.
- After the loop, initialize a counter `count` to 0.
- Iterate over the values (the `Set<Character>`) of the `rods` map.
- If a set's size is 3, it means all three colors are present, so increment `count`.
- Return `count`.

## Using an Array of Sets
This approach is an optimization of the Hash Map method. Since the rods are labeled from 0 to 9, we can use a fixed-size array of size 10 instead of a Hash Map. Each index in the array corresponds to a rod, and the element at that index is a Set containing the colors of rings on that rod. This avoids the overhead of hashing.
**Time:** O(N), where N is the length of the `rings` string. The processing is dominated by the single pass through the input string. Array access is O(1). · **Space:** O(1) - Constant space. The space is fixed by the number of rods (10) and colors (3), so it does not depend on the input size N.
**Pros:** More efficient than the Hash Map approach due to direct array indexing, which avoids hashing overhead.; Maintains good readability while improving performance.; Constant space complexity.
**Cons:** Still involves the overhead of creating and managing `HashSet` objects.; This approach is less flexible than a map if the rod indices were not small, consecutive integers.
### Explanation
Knowing there are exactly 10 rods (0-9) allows us to use an array for direct, constant-time access, which is generally faster than hash map lookups.

1.  Initialize an array of `Set<Character>` of size 10. It's crucial to also initialize each element of this array with a new `HashSet` instance.
2.  Iterate through the `rings` string in pairs. For each color-rod pair, parse the rod index.
3.  Use the rod index to directly access the corresponding set in our array and add the color to it.
4.  After populating the array with all the color information, iterate through the array from index 0 to 9.
5.  For each of the 10 sets, check if its size is 3.
6.  The total count of sets with size 3 is the number of rods with all three colors.

```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    public int countPoints(String rings) {
        // Array of sets, one for each rod (0-9)
        Set<Character>[] rods = new Set[10];
        for (int i = 0; i < 10; i++) {
            rods[i] = new HashSet<>();
        }
        
        // Iterate through the rings string
        for (int i = 0; i < rings.length(); i += 2) {
            char color = rings.charAt(i);
            int rodIndex = rings.charAt(i + 1) - '0';
            
            // Add the color to the set for the corresponding rod
            rods[rodIndex].add(color);
        }
        
        int count = 0;
        // Count rods with all three colors
        for (int i = 0; i < 10; i++) {
            if (rods[i].size() == 3) {
                count++;
            }
        }
        
        return count;
    }
}
```
### Algorithm
- Create an array of `Set<Character>` of size 10, named `rods`.
- Initialize each element of the `rods` array with a new `HashSet`.
- Loop through the `rings` string with a step of 2.
- In each iteration, extract the `color` and `rodIndex`.
- Add the `color` to the set at `rods[rodIndex]`.
- Initialize a counter `count` to 0.
- Loop from `i = 0` to 9.
- If `rods[i].size()` is 3, increment `count`.
- Return `count`.

## Bitmasking Approach
This is the most efficient approach in terms of both space and practical speed. It uses an integer array of size 10 to represent the rods. Each integer acts as a bitmask to store the presence of colors. Specific bits are assigned to each color (e.g., Red=1, Green=2, Blue=4). A rod has all three colors if its corresponding integer value becomes 7 (which is the result of `1 | 2 | 4`).
**Time:** O(N), where N is the length of the `rings` string. The single pass through the string is the dominant operation, and all operations inside the loop are constant time. · **Space:** O(1) - Constant space. We only use a fixed-size integer array of size 10.
**Pros:** Extremely space-efficient, using only a small, primitive integer array.; Very fast due to the use of primitive types and bitwise operations, which are highly optimized at the hardware level.; Minimal object creation overhead.
**Cons:** The logic might be slightly less intuitive for developers not comfortable with bit manipulation.; Less extensible if the number of colors were to increase significantly.
### Explanation
This method leverages bit manipulation for a compact and fast solution. We can represent the presence of the three colors (R, G, B) using 3 distinct bits of an integer.

-   Assign a bit for each color:
    -   'R' -> bit 0 (value 1, i.e., `1 << 0`)
    -   'G' -> bit 1 (value 2, i.e., `1 << 1`)
    -   'B' -> bit 2 (value 4, i.e., `1 << 2`)

1.  We use an integer array `rods` of size 10, initialized to all zeros. `rods[i]` will store the combined color information for rod `i` as a bitmask.
2.  We iterate through the `rings` string. For each ring, we identify its color and rod index.
3.  We then set the corresponding bit in the integer for that rod using the bitwise OR operator (`|=`). For example, if we find a red ring ('R') on rod 3, we perform `rods[3] |= 1`. If we later find a green ring ('G') on the same rod, we perform `rods[3] |= 2`. The value of `rods[3]` would then be `1 | 2 = 3`.
4.  After processing all rings, a rod `i` has all three colors if and only if all three bits (0, 1, and 2) are set in `rods[i]`. This corresponds to the integer value `1 | 2 | 4 = 7`.
5.  Finally, we iterate through the `rods` array and count how many elements are equal to 7. This count is our result.

```java
class Solution {
    public int countPoints(String rings) {
        // Each element represents a rod. We use bits to store colors.
        // bit 0: Red, bit 1: Green, bit 2: Blue
        int[] rods = new int[10];
        
        for (int i = 0; i < rings.length(); i += 2) {
            char color = rings.charAt(i);
            int rodIndex = rings.charAt(i + 1) - '0';
            
            int mask = 0;
            if (color == 'R') {
                mask = 1; // binary 001
            } else if (color == 'G') {
                mask = 2; // binary 010
            } else if (color == 'B') {
                mask = 4; // binary 100
            }
            
            // Use bitwise OR to set the color bit for the rod
            rods[rodIndex] |= mask;
        }
        
        int count = 0;
        // The mask for all three colors is 1 | 2 | 4 = 7
        int allColorsMask = 7;
        for (int rodColors : rods) {
            if (rodColors == allColorsMask) {
                count++;
            }
        }
        
        return count;
    }
}
```
### Algorithm
- Create an integer array `rods` of size 10, initialized to all zeros.
- Loop through the `rings` string with a step of 2.
- Extract the `color` and `rodIndex`.
- Determine the bitmask for the color: 1 for 'R', 2 for 'G', 4 for 'B'.
- Update the rod's state using a bitwise OR operation: `rods[rodIndex] |= mask`.
- After the loop, initialize a counter `count` to 0.
- Loop through the `rods` array.
- If an element's value is 7 (which is `1 | 2 | 4`), it means all three color bits are set, so increment `count`.
- Return `count`.

# Solutions
### Java

```java
class Solution {
public
  int countPoints(String rings) {
    int[] d = new int['Z'];
    d['R'] = 1;
    d['G'] = 2;
    d['B'] = 4;
    int[] mask = new int[10];
    for (int i = 0, n = rings.length(); i < n; i += 2) {
      int c = rings.charAt(i);
      int j = rings.charAt(i + 1) - '0';
      mask[j] |= d[c];
    }
    int ans = 0;
    for (int x : mask) {
      if (x == 7) {
        ++ans;
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution { public: int countPoints ( string rings ) { int d [ 'Z' ]{[ 'R' ] = 1 , [ 'G' ] = 2 , [ 'B' ] = 4 }; int mask [ 10 ]{}; for ( int i = 0 , n = rings . size (); i < n ; i += 2 ) { int c = rings [ i ]; int j = rings [ i + 1 ] - '0' ; mask [ j ] |= d [ c ]; } return count ( mask , mask + 10 , 7 ); } };
```

### Python

```python
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 )
```