algoadvance

Leetcode 2103. Rings and Rods

Problem Statement

You are given a string rings of length 2n that consists of lowercase English letters and numbers. This string represents n rods that are placed in a row, and the positions of the characters in the string represent which rods are attached with rings.

• rings consist of characters from the set {‘R’, ‘G’, ‘B’} denoting the color of the rings (Red, Green, Blue) and digits from the set {‘0’-‘9’} denoting the rod number.
• The sequence in the string is such that characters at even indices are colors, and characters at odd indices are their corresponding rod numbers.

A rod is considered fully decorated if it has all three colors of rings: Red (R), Green (G), and Blue (B).

Return the number of rods that are fully decorated.

Constraints:

• rings.length == 2 * n
• 1 <= n <= 100
• rings[i] where i is even is either ‘R’, ‘G’, or ‘B’
• rings[i] where i is odd is a digit from ‘0’ to ‘9’

Clarifying Questions

1. Q: Are there always axes at positions and corresponding rods, or can some rods be missing in the input string? A: Since the input is always provided in pairs, every rod number mentioned must correspond to a color, so no rods are missing.

2. Q: What should be done if a rod doesn’t have any of the colors? A: Only fully decorated rods (those with all three colors) need to be counted.

3. Q: Is the order of characters in the string always going to be valid in terms of alternating indices for colors and rod numbers? A: Yes, the problem constraints ensure that the string length is even, and characters at even indices are colors and at odd indices are digits.

Strategy

1. Initialize a data structure (e.g., an array of sets or a hashmap) to keep track of the colors on each rod.
2. Traverse the string in pairs: one for color and the next for the rod number.
3. Update the data structure to insert the color for the corresponding rod.
4. Iterate through the data structure to count how many rods have all three colors.
5. Return the count of fully decorated rods.

Code

#include <iostream>
#include <unordered_map>
#include <unordered_set>
#include <string>

int countPoints(std::string rings) {
    // Dictionary to hold the sets of colors for each rod
    std::unordered_map<char, std::unordered_set<char>> rod_colors;
    
    // Iterate through the string in pairs
    for (size_t i = 0; i < rings.size(); i += 2) {
        char color = rings[i];
        char rod = rings[i + 1];
        rod_colors[rod].insert(color);
    }
    
    int fully_decorated_count = 0;
    
    // Check for fully decorated rods
    for (const auto& entry : rod_colors) {
        if (entry.second.size() == 3) {
            fully_decorated_count++;
        }
    }
    
    return fully_decorated_count;
}

int main() {
    std::string rings = "B0R0G0R1B1G1B2R2R3B3G3";
    std::cout << countPoints(rings) << std::endl; // Expect output: 3
    return 0;
}

Time Complexity

• Insertion into the map: O(1) for each pair of color and rod number.
• Iteration through the string: This runs in O(n) time where n is half the length of the input string.
• Final iteration to count fully decorated rods: It will iterate at most 10 rods, hence O(1).

Overall, the time complexity is O(n), where n is half the length of the input string.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?