# LeetCode 800: Similar RGB Color

## Problem Restatement

We are given a color string in this format:

```python
"#ABCDEF"
```

The color has three hexadecimal components:

| Component | Meaning |
|---|---|
| `AB` | Red |
| `CD` | Green |
| `EF` | Blue |

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

For example:

```python
"#AABBCC"
```

can be written as:

```python
"#ABC"
```

because:

```text
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

| Item | Meaning |
|---|---|
| Input | A string `color` in the format `"#ABCDEF"` |
| Output | A 7-character shorthand-compatible color |
| Shorthand-compatible pair | One of `00`, `11`, `22`, ..., `ff` |
| Goal | Minimize RGB squared difference |

Function shape:

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

## Examples

Example 1:

```python
color = "#09f166"
```

The best shorthand-compatible color is:

```python
"#11ee66"
```

Why?

| Original | Closest shorthand pair |
|---|---|
| `09` | `11` |
| `f1` | `ee` |
| `66` | `66` |

So the answer is:

```python
"#11ee66"
```

Example 2:

```python
color = "#abcdef"
```

Check each pair:

| Original | Decimal | Closest shorthand pair |
|---|---:|---|
| `ab` | `171` | `aa` |
| `cd` | `205` | `cc` |
| `ef` | `239` | `ee` |

So one nearest shorthand-compatible color is:

```python
"#aaccee"
```

## First Thought: Try All Shorthand Colors

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

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

So there are:

```text
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:

```text
-(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:

```text
00, 11, 22, ..., ff
```

In decimal, these are:

```text
0, 17, 34, 51, ..., 255
```

Each value is a multiple of `17`, because:

```python
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:

```python
"f1" -> 241
```

The nearest multiples of `17` are:

```text
238 = 0xee
255 = 0xff
```

`238` is closer, so the result is:

```python
"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

| Metric | Value | Why |
|---|---|---|
| Time | `O(1)` | There are always exactly three color channels |
| Space | `O(1)` | Only a few strings and integers are stored |

## Implementation

```python
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:

```python
"09"
```

It converts the pair from hexadecimal to decimal:

```python
value = int(pair, 16)
```

Then it finds the nearest shorthand index:

```python
index = round(value / 17)
```

The index is between `0` and `15`.

We convert that index back to a hexadecimal digit:

```python
digit = format(index, "x")
```

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

```python
return digit + digit
```

Finally, we process all three channels:

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

and build the final color:

```python
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:

```python
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

```python
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:

| Test | Why |
|---|---|
| `#09f166` | Standard example |
| `#abcdef` | Mixed hexadecimal letters |
| `#000000` | Lower boundary |
| `#ffffff` | Upper boundary |
| `#123456` | Regular rounding across all channels |
| `#010203` | Small values round down |