LeetCode 800 - Similar RGB Color

Difficulty: 🟢 Easy
Topics: Math, String, Enumeration

Solution

Problem Understanding

The problem is asking us to find the shorthand RGB color that is most similar to a given full-length RGB color string. An RGB color is represented as a hexadecimal string of the form "#RRGGBB", where each pair of characters (RR, GG, BB) represents the red, green, and blue components, respectively, using two hexadecimal digits. A shorthand version compresses each component to a single hex digit repeated twice, i.e., "#RGB" represents "#RRGGBB" as RR = R*16 + R, GG = G*16 + G, and BB = B*16 + B.

The similarity between two colors "#ABCDEF" and "#UVWXYZ" is measured using the negative sum of squared differences for each color component:

similarity = -(AB - UV)^2 - (CD - WX)^2 - (EF - YZ)^2

The goal is to find a shorthand color that maximizes this similarity (equivalently, minimizes the sum of squared differences for each color component).

The input color is guaranteed to be a valid 7-character string starting with #, and every other character is a hexadecimal digit from 0-9 or a-f. This constraint ensures that we do not need to handle invalid or malformed input. Important edge cases include colors where one or more components are already close to a multiple of 17 (the possible shorthand increments), and colors at the extremes like "#000000" or "#ffffff".

Approaches

Brute Force Approach

A brute-force approach would be to enumerate all possible shorthand colors. Each component has 16 possible shorthand values (0x00, 0x11, ..., 0xff), so there are 16 * 16 * 16 = 4096 potential shorthand colors. For each candidate, we calculate the similarity with the input color and keep track of the one with the maximum similarity. This approach is correct because it exhaustively checks every possible shorthand color but is unnecessary given the structured nature of shorthand colors.

Optimal Approach

The key observation is that each shorthand color component has the form xx in hexadecimal, which corresponds to x*16 + x in decimal. Therefore, for each component of the input color (a two-digit hex), the most similar shorthand digit can be found independently by minimizing the difference between the actual value and x*17 (because x*16 + x = x*17). This reduces the problem to processing each component separately instead of enumerating all combinations.

The optimal approach, therefore, converts each two-digit hex component to decimal, finds the closest multiple of 17, converts it back to a repeated hex digit, and constructs the shorthand color.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(4096)	O(1)	Enumerates all shorthand combinations and selects the best
Optimal	O(1)	O(1)	Computes closest shorthand digit for each component independently

Algorithm Walkthrough

Extract the red, green, and blue components from the input string by slicing it into color[1:3], color[3:5], and color[5:7].
Convert each two-character hex component to a decimal integer using base 16.
For each component value, compute the closest shorthand value. Since shorthand values are multiples of 17 (i.e., 0, 17, 34, ..., 255), divide the decimal component by 17, round to the nearest integer x, and compute x*17.
Convert the resulting integer back to a hex string of length 2 by repeating the hex digit corresponding to x.
Concatenate the three shorthand components with a # prefix to form the final color string.
Return the constructed shorthand color.

Why it works: The algorithm works because each color component is independent in the similarity formula. The sum of squared differences is minimized component-wise by picking the multiple of 17 closest to the original component, ensuring the overall similarity is maximized. This avoids unnecessary enumeration of all combinations while guaranteeing the optimal shorthand color.

Python Solution

class Solution:
    def similarRGB(self, color: str) -> str:
        def closest_shorthand_component(comp: str) -> str:
            value = int(comp, 16)
            x = round(value / 17)
            shorthand_value = x * 17
            return f'{shorthand_value:02x}'
        
        r = closest_shorthand_component(color[1:3])
        g = closest_shorthand_component(color[3:5])
        b = closest_shorthand_component(color[5:7])
        
        return f'#{r}{g}{b}'

The closest_shorthand_component function handles a single color component. It converts the two-character hex string to decimal, divides by 17 and rounds to find the closest shorthand component, and formats it back to a two-character hex string. Each color component of the input is processed separately, then combined to form the final result.

Go Solution

import (
    "fmt"
    "strconv"
)

func similarRGB(color string) string {
    closestShorthand := func(comp string) string {
        val, _ := strconv.ParseInt(comp, 16, 0)
        x := int((val + 8) / 17)
        shorthandVal := x * 17
        return fmt.Sprintf("%02x", shorthandVal)
    }

    r := closestShorthand(color[1:3])
    g := closestShorthand(color[3:5])
    b := closestShorthand(color[5:7])

    return "#" + r + g + b
}

The Go implementation uses strconv.ParseInt to convert hex strings to integers. It uses (val + 8)/17 instead of round(val/17) to achieve rounding to the nearest integer. The rest mirrors the Python logic, constructing the final color by concatenating the shorthand components.

Worked Examples

Example 1

Input: "#09f166"

Red component "09" → 9 → round(9/17)=1 → 1*17=17 → hex "11"
Green component "f1" → 241 → round(241/17)=14 → 14*17=238 → hex "ee"
Blue component "66" → 102 → round(102/17)=6 → 6*17=102 → hex "66"

Output: "#11ee66"

Example 2

Input: "#4e3fe1"

Red "4e" → 78 → round(78/17)=5 → 5*17=85 → hex "55"
Green "3f" → 63 → round(63/17)=4 → 4*17=68 → hex "44"
Blue "e1" → 225 → round(225/17)=13 → 13*17=221 → hex "dd"

Output: "#5544dd"

Complexity Analysis

Measure	Complexity	Explanation
Time	O(1)	Only three color components are processed independently; all operations are constant time
Space	O(1)	Only a few variables are used for computation; no dynamic data structures needed

The algorithm scales in constant time because the input size is fixed and independent of any larger parameters.

Test Cases

# Provided examples
assert Solution().similarRGB("#09f166") == "#11ee66"  # basic example
assert Solution().similarRGB("#4e3fe1") == "#5544dd"  # basic example

# Edge cases
assert Solution().similarRGB("#000000") == "#000000"  # all zeros
assert Solution().similarRGB("#ffffff") == "#ffffff"  # all max
assert Solution().similarRGB("#010101") == "#000000"  # very small values
assert Solution().similarRGB("#fefefe") == "#ffffff"  # very high values
assert Solution().similarRGB("#123456") == "#112233"  # arbitrary input
assert Solution().similarRGB("#abcdef") == "#aabbcc"  # arbitrary input

Test	Why
`"#09f166"`	verifies normal calculation with rounding
`"#4e3fe1"`	checks multiple rounding cases for all components
`"#000000"`	minimum color values
`"#ffffff"`	maximum color values
`"#010101"`	very small numbers rounded down
`"#fefefe"`	very large numbers rounded up
`"#123456"`	arbitrary middle-range input
`"#abcdef"`	arbitrary middle-range input

Edge Cases

All zeros (#000000): This tests if the function correctly handles the minimum input values. The algorithm rounds 0/17 = 0, so the output remains #000000.
All maximum (#ffffff): This tests if the function handles the largest possible input. Each component 255/17 ≈ 15 rounds correctly to 15*17=255, so the output remains #ffffff.
Rounding boundary (#010101 and #fefefe): These test rounding behavior for components close to the boundary between two shorthand values. For example, 0x01/17 ≈ 0.0588, which rounds down to