We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Rings and Rods

Difficulty: Easy

Problem Description

You are given a string rings of length 2n that describes n rings placed on ten rods labeled from 0 to 9. Each ring is represented by a color-position pair, where the first character denotes the ring's color (either 'R', 'G', or 'B') and the second character denotes the rod it is placed on. The goal is to return the number of rods that have all three colors of rings on them.

Key Insights

  • Each pair of characters in the input string represents a ring's color and its corresponding rod.
  • We need to keep track of which colors are present on each rod.
  • A rod is considered to have all three colors if it has at least one ring of each color.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1) (constant space for the fixed number of rods)

Solution

To solve the problem, we can use a hash table (or an array) to keep track of the colors present on each of the ten rods. We will iterate through the input string two characters at a time, updating our data structure accordingly. At the end, we will count how many rods have all three colors.

  1. Initialize an array of sets with a size of 10, where each set will hold the colors present on that rod.
  2. Loop through the input string in steps of 2 to read the color and the corresponding rod.
  3. Add the color to the appropriate set based on the rod.
  4. After processing all rings, count how many sets contain all three colors.

Code Solutions

def countPoints(rings: str) -> int:
    # Create an array of sets for each rod
    rods = [set() for _ in range(10)]
    
    # Iterate through the rings in pairs
    for i in range(0, len(rings), 2):
        color = rings[i]
        rod = int(rings[i + 1])
        # Add the color to the corresponding rod set
        rods[rod].add(color)
    
    # Count rods with all three colors
    return sum(1 for rod in rods if len(rod) == 3)
← Back to All Questions