algoadvance

You are given a string rings representing the placement of rings on rods. The string contains the characters ‘R’, ‘G’, ‘B’ (representing the colors of the rings: red, green, and blue) and digits ‘0’ to ‘9’ (representing the rods). Each ring is described by exactly two characters: its color and the rod it is placed on.

For example, the string "B0R0G0R9B9G9" means there is a blue ring on rod 0, a red ring on rod 0, a green ring on rod 0, a red ring on rod 9, a blue ring on rod 9, and a green ring on rod 9.

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

Example 1:

Input: rings = "B0R0G0R9B9G9"
Output: 2
Explanation: 
- Rod 0 has all three colors: red, green, and blue.
- Rod 9 has all three colors: red, green, and blue.
- Thus, there are 2 rods with all three colors of rings.

Example 2:

Input: rings = "B0R0G0R1G0B1"
Output: 1
Explanation: 
- Rod 0 has all three colors: red, green, and blue.
- Rod 1 lacks a green ring. 
- Thus, there is only 1 rod with all three colors of rings.

Clarifying Questions

  1. Is the input string always guaranteed to be valid according to the problem description?
    • Yes, the input string is guaranteed to follow the format described.
  2. Is the order of the characters in the input string important?
    • No, the order doesn’t matter; we just need to count the colors per rod.
  3. Are we supposed to consider uppercase and lowercase characters?
    • The problem states ‘R’, ‘G’, ‘B’, and digits ‘0’ to ‘9’, so we only need to handle these specific characters.

Strategy

  1. Parse the input string in steps of two characters.
  2. Use a dictionary to keep track of unique colors for each rod.
  3. For each pair (color, rod), add the color to the set of that specific rod.
  4. After processing the entire string, count how many rods have sets containing all three colors.

Code

def countPoints(rings: str) -> int:
    rod_colors = {}

    for i in range(0, len(rings), 2):
        color = rings[i]
        rod = rings[i + 1]

        if rod not in rod_colors:
            rod_colors[rod] = set()
        
        rod_colors[rod].add(color)
    
    count = 0

    for colors in rod_colors.values():
        if len(colors) == 3:
            count += 1

    return count

# Example usage:
assert countPoints("B0R0G0R9B9G9") == 2
assert countPoints("B0R0G0R1G0B1") == 1

Time Complexity

Try our interview co-pilot at AlgoAdvance.com