> For the complete documentation index, see [llms.txt](https://protegejj.gitbook.io/algorithm-practice/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://protegejj.gitbook.io/algorithm-practice/google/800-similar-rgb-color.md).

# 800 Similar RGB Color

## 800.[ Similar RGB Color](https://leetcode.com/problems/similar-rgb-color/description/)

## 1. Question

In the following, every capital letter represents some hexadecimal digit from`0`to`f`.

The red-green-blue color`"#AABBCC"` can be written as `"#ABC"`in shorthand. For example,`"#15c"`is shorthand for the color`"#1155cc"`.

Now, say the similarity between two colors`"#ABCDEF"`and`"#UVWXYZ"`is`-(AB - UV)^2 - (CD - WX)^2 - (EF - YZ)^2`.

Given the color`"#ABCDEF"`, return a 7 character color that is most similar to`#ABCDEF`, and has a shorthand (that is, it can be represented as some`"#XYZ"`

```
Example 1:
Input:
 color = "#09f166"

Output: "#11ee66"

Explanation: 
The similarity is -(0x09 - 0x11)^2 -(0xf1 - 0xee)^2 - (0x66 - 0x66)^2 = -64 -9 -0 = -73.
This is the highest among any shorthand color.
```

**Note:**

* `color`is a string of length`7`.
* `color`is a valid RGB color: for`i > 0`,`color[i]`is a hexadecimal digit from`0`to`f`
* Any answer which has the same (highest) similarity as the best answer will be accepted.
* All inputs and outputs should use lowercase letters, and the output is 7 characters.

## 2. Implementation

思路: 这道题的关键是要知道

(1) RGB三种颜色所对应的hexadecimal是可以分别计算的，也就是从color的第2位开始没隔两位的找出离它们最接近的hexadecimal

(2) 由于题目中表明要找出有shorthand的16进制(RGB三种颜色所对应的16进制数每位都一样，如11，22，ff)，且我们发现这些有shorthand的16进制数每个之间的差刚好等于17，如数组\[0, 17, 34, 51 ... 255]，这给我们的启示是给定一个16进制数，将其转为10进制后num, 那么其最接近它的数 应该是在index = num / 17这个位置上，但这里要注意的是，我们还需要检查余数 num % 17, 确保余数是小于8的 (17的一半), 否则index要加1。举个例子，给定10进制数29，index = 29/17 = 1, 但事实上34比17更加接近29

```java
class Solution {
    public String similarRGB(String color) {
        StringBuilder res = new StringBuilder();
        res.append("#");

        for (int i = 1; i < color.length(); i += 2) {
            res.append(getHexDigits(color.charAt(i), color.charAt(i + 1)));
        }
        return res.toString();
    }

    public String getHexDigits(char c1, char c2) {
        int digit1 = Character.isDigit(c1) ? c1 - '0' : 10 + c1 - 'a';
        int digit2 = Character.isDigit(c2) ? c2 - '0' : 10 + c2 - 'a';

        int num = digit1 * 16 + digit2;
        int index = num / 17;
        if (num % 17 > 8) {
            ++index;
        }
        char c = '0';

        if (index >= 10) {
            c = (char)('a' + index - 10);
        }
        else {
            c = (char)('0' + index);
        }
        return String.valueOf(c) + String.valueOf(c);
    }
}
```

## 3. Time & Space Complexity

时间复杂度O(n), n是color的长度，但因为color的长度固定为7，所以严格来说时间复杂度是O(1), 同理空间复杂度是O(1)