LeetCode 800: Similar RGB Color

Problem Restatement

We are given a color string in this format:

"#ABCDEF"

The color has three hexadecimal components:

A color has shorthand form if each component has two equal hexadecimal digits.

For example:

"#AABBCC"

can be written as:

"#ABC"

because:

AA -> A
BB -> B
CC -> C

We need to return a 7-character color string that has shorthand form and is most similar to the given color.

Similarity is based on minimizing the squared distance between the three RGB components.

Input and Output

Function shape:

class Solution:
    def similarRGB(self, color: str) -> str:
        ...

Examples

Example 1:

color = "#09f166"

The best shorthand-compatible color is:

"#11ee66"

Why?

So the answer is:

"#11ee66"

Example 2:

color = "#abcdef"

Check each pair:

So one nearest shorthand-compatible color is:

"#aaccee"

First Thought: Try All Shorthand Colors

There are only 16 possible shorthand-compatible values for each color channel:

00, 11, 22, 33, 44, 55, 66, 77,
88, 99, aa, bb, cc, dd, ee, ff

So there are:

16 * 16 * 16 = 4096

possible shorthand RGB colors.

We could try all of them, compute the similarity score, and return the best one.

This works because the search space is small.

But we can do even simpler by solving each channel independently.

Key Insight

The similarity formula is:

-(R1 - R2)^2 - (G1 - G2)^2 - (B1 - B2)^2

The three channels are independent.

So to maximize similarity, we minimize the squared difference for each channel separately.

A shorthand-compatible channel must be one of:

00, 11, 22, ..., ff

In decimal, these are:

0, 17, 34, 51, ..., 255

Each value is a multiple of 17, because:

0x11 == 17

So for a channel value x, we need the nearest multiple of 17.

Algorithm

For each channel pair:

1. Convert the two-character hex string to an integer.
2. Round it to the nearest multiple of 17.
3. Convert that multiple back to one repeated hex digit.

For example:

"f1" -> 241

The nearest multiples of 17 are:

238 = 0xee
255 = 0xff

238 is closer, so the result is:

"ee"

Correctness

A shorthand-compatible color must have each channel equal to one of 00, 11, 22, …, ff.

These channel values are exactly the multiples of 17 from 0 through 255.

The total squared difference is the sum of the squared differences of the red, green, and blue channels. Since each channel contributes independently to the sum, choosing the closest shorthand-compatible value for each channel minimizes the total squared difference.

The algorithm converts each channel to decimal, rounds it to the nearest multiple of 17, and emits the corresponding repeated hexadecimal digit. Therefore, each output channel is shorthand-compatible and has the smallest possible squared difference from the input channel.

Thus, the combined color is the most similar shorthand-compatible color.

Complexity

Implementation

class Solution:
    def similarRGB(self, color: str) -> str:
        def closest(pair: str) -> str:
            value = int(pair, 16)
            index = round(value / 17)
            digit = format(index, "x")
            return digit + digit

        red = closest(color[1:3])
        green = closest(color[3:5])
        blue = closest(color[5:7])

        return "#" + red + green + blue

Code Explanation

The helper receives one channel, such as:

"09"

It converts the pair from hexadecimal to decimal:

value = int(pair, 16)

Then it finds the nearest shorthand index:

index = round(value / 17)

The index is between 0 and 15.

We convert that index back to a hexadecimal digit:

digit = format(index, "x")

Then repeat the digit to form a shorthand-compatible pair:

return digit + digit

Finally, we process all three channels:

red = closest(color[1:3])
green = closest(color[3:5])
blue = closest(color[5:7])

and build the final color:

return "#" + red + green + blue

Safer Rounding Version

Python’s round uses banker’s rounding for exact .5 cases. This problem does not create an exact .5 when dividing an integer by 17, so it is safe here.

Still, we can write explicit nearest-integer rounding:

class Solution:
    def similarRGB(self, color: str) -> str:
        def closest(pair: str) -> str:
            value = int(pair, 16)
            index = (value + 8) // 17
            digit = format(index, "x")
            return digit + digit

        return (
            "#"
            + closest(color[1:3])
            + closest(color[3:5])
            + closest(color[5:7])
        )

This version rounds to the nearest multiple of 17 using integer arithmetic.

Testing

def run_tests():
    s = Solution()

    assert s.similarRGB("#09f166") == "#11ee66"
    assert s.similarRGB("#abcdef") == "#aaccee"
    assert s.similarRGB("#000000") == "#000000"
    assert s.similarRGB("#ffffff") == "#ffffff"
    assert s.similarRGB("#123456") == "#113355"
    assert s.similarRGB("#010203") == "#000000"

    print("all tests passed")

run_tests()

Test coverage: