Problem Description

The Similar RGB Color problem requires you to find the closest shorthand color for a given 6-digit RGB hexadecimal color code. The input is a string color that starts with '#' and is followed by six hexadecimal digits (e.g., #09f166).

In shorthand RGB notation, each color component (red, green, blue) is represented by two identical hex digits (e.g., #11aa77 becomes #1a7). A shorthand color always looks like ##XXYYZZ where XX, YY, and ZZ are two identical hex digits each.

Your task is: for the given color, return the shorthand color that is most similar (minimizes the sum of squared differences for each RGB component). There is always exactly one valid answer for each input.

Thought Process

At first, you might think to try all possible shorthand colors and check which is closest to the input color. However, this would be inefficient. Instead, notice that for each color component (red, green, blue), we only need to find the closest pair of identical hex digits (like 00, 11, ..., ff) to the original component.

In other words, for each two-digit color component, we want to find the value of xx (where both digits are the same) that is closest to the original value. Since there are only 16 possible shorthand values (from 00 to ff), we can compute this efficiently.

This approach avoids brute-force over the entire color space and focuses on optimizing each component independently.

Solution Approach

• Step 1: For each color component (red, green, blue), extract the two hex digits from the input string.
• Step 2: Convert the two-digit hex string to its decimal value.
• Step 3: For each component, find the shorthand hex value that is closest. Shorthand values are 0x00, 0x11, 0x22, ..., 0xff (i.e., multiples of 17).
• Step 4: To find the nearest shorthand value, round the original component value to the nearest multiple of 17.
• Step 5: Convert the resulting value back to a two-digit hex string (with both digits the same).
• Step 6: Concatenate the results for red, green, and blue, and prefix with '#' to get the final answer.

This method ensures that for each color component, you pick the most similar shorthand value, and thus the overall color is the closest possible shorthand color.

Example Walkthrough

Input: #09f166

1. Red component: 09 (decimal 9)
   • Possible shorthand values: 0, 17, 34, ..., 255
   • Closest is 0 (since 9 is closer to 0 than 17)
   • So, shorthand is 00
2. Green component: f1 (decimal 241)
   • Closest multiple of 17: 238 (17 * 14 = 238), next is 255
   • 241 - 238 = 3, 255 - 241 = 14, so 238 is closer
   • So, shorthand is ee
3. Blue component: 66 (decimal 102)
   • Closest multiple of 17: 102 (17 * 6 = 102)
   • So, shorthand is 66

Final output: #00ee66

Code Implementation

class Solution:
    def similarRGB(self, color: str) -> str:
        def getClosest(s):
            val = int(s, 16)
            idx = int((val + 8) / 17)
            closest = 17 * idx
            return '{:02x}'.format(closest)
        return '#' + ''.join(getClosest(color[i:i+2]) for i in (1, 3, 5))
      

class Solution {
public:
    string similarRGB(string color) {
        auto getClosest = [](string s) {
            int val = stoi(s, nullptr, 16);
            int idx = (val + 8) / 17;
            int closest = 17 * idx;
            char buf[3];
            sprintf(buf, "%02x", closest);
            return string(buf);
        };
        string res = "#";
        for (int i = 1; i < color.size(); i += 2) {
            res += getClosest(color.substr(i, 2));
        }
        return res;
    }
};
      

class Solution {
    public String similarRGB(String color) {
        StringBuilder res = new StringBuilder("#");
        for (int i = 1; i < color.length(); i += 2) {
            String s = color.substring(i, i+2);
            int val = Integer.parseInt(s, 16);
            int idx = (val + 8) / 17;
            int closest = 17 * idx;
            res.append(String.format("%02x", closest));
        }
        return res.toString();
    }
}
      

var similarRGB = function(color) {
    function getClosest(s) {
        let val = parseInt(s, 16);
        let idx = Math.floor((val + 8) / 17);
        let closest = 17 * idx;
        let hex = closest.toString(16);
        if (hex.length < 2) hex = '0' + hex;
        return hex;
    }
    return '#' + getClosest(color.slice(1,3)) + getClosest(color.slice(3,5)) + getClosest(color.slice(5,7));
};
      

Time and Space Complexity

• Brute-force Approach: If you tried every possible shorthand color (16³ = 4096), you'd have O(1) time (since 4096 is constant), but this is still unnecessary work.
• Optimized Approach: For each component, you do a simple calculation and string manipulation, so the total time is O(1).
• Space Complexity: Both approaches use O(1) extra space, as only a few variables are needed.

The optimized approach is both faster and cleaner, taking constant time and space.

Summary

The key insight is that for each color component, the closest shorthand value is the nearest multiple of 17. By rounding each component to the nearest such value, we efficiently construct the most similar shorthand color. This approach is elegant because it leverages the structure of hexadecimal shorthand notation and avoids unnecessary brute-force computation.