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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Rings and Rods

Number: 2226

Difficulty: Easy

Paid? No

Companies: Google

Problem Description

You are given a string representing rings placed on ten rods (labeled 0-9). Each ring is specified as a two-character pair where the first character is the color ('R', 'G', or 'B') and the second is the rod number. The task is to determine how many rods have rings of all three colors.

Key Insights

  • Use a hash table (dictionary) to map each rod to the set of colors that appear on it.
  • Iterate over the string in steps of two to process each ring's color and rod number.
  • Count a rod only if its corresponding set contains all three colors.

Space and Time Complexity

Time Complexity: O(n), where n is the number of rings (processing each pair once).
Space Complexity: O(1), since there are only 10 rods and at most 3 colors per rod.

Solution

We can solve the problem by iterating over the given rings string two characters at a time. For each ring, insert the ring's color into a set associated with the rod number in a dictionary. After processing all rings, count how many rods have a set size of exactly 3 (indicating all colors are present). This approach leverages a hash table (dictionary) and the properties of sets to avoid duplicates, making it efficient and straightforward.

Code Solutions

# Python solution with line-by-line comments

def countPoints(rings: str) -> int:
    # Create a dictionary to map rod number to a set of colors present on it
    rod_colors = {}
    
    # Iterate over the rings string in steps of 2 (each pair is color and rod)
    for i in range(0, len(rings), 2):
        color = rings[i]        # The color of the ring (R, G, or B)
        rod = rings[i+1]        # The rod number as a character
        
        # If rod is not in the dictionary, initialize its value as an empty set
        if rod not in rod_colors:
            rod_colors[rod] = set()
        
        # Add the color to the set corresponding to the rod
        rod_colors[rod].add(color)
    
    # Count and return the number of rods that have all three colors by checking if set size equals 3
    return sum(1 for colors in rod_colors.values() if len(colors) == 3)

# Example usage:
rings_input = "B0B6G0R6R0R6G9"
print(countPoints(rings_input))  # Expected output: 1
← Back to All Questions