Problem

The red-green-blue color "#AABBCC" can be written as "#ABC" in shorthand.

  • For example, "#15c" is shorthand for the color "#1155cc".

The similarity between the two colors "#ABCDEF" and "#UVWXYZ" is -(AB -UV)2 - (CD - WX)2 - (EF - YZ)2.

Given a string color that follows the format "#ABCDEF", return a string represents the color that is most similar to the given color and has a shorthand (i.e., it can be represented as some "#XYZ").

Any answer which has the same highest similarity as the best answer will be accepted.

Examples

Example 1:

1
2
3
4
5

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.

Example 2:

1
2

Input: color = "#4e3fe1"
Output: "#5544dd"

Constraints:

  • color.length == 7
  • color[0] == '#'
  • color[i] is either digit or character in the range ['a', 'f'] for i > 0.

Solution

Method 1 – Brute Force Over Shorthand Candidates

Intuition

For each color component (RR, GG, BB), the closest shorthand is of the form “xx” (where x is a hex digit), i.e., 0x11, 0x22, …, 0xFF. For each component, find the shorthand value closest to the original.

Approach

  1. For each component (RR, GG, BB), parse the two hex digits.
  2. For each, find the closest value of the form x*17 (i.e., 0x00, 0x11, …, 0xFF).
  3. Build the result string as “#XXYYZZ” where each pair is the closest shorthand.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

#include <string>
#include <sstream>
using namespace std;
class Solution {
public:
    string similarRGB(string color) {
        string res = "#";
        for (int i = 1; i < 7; i += 2) {
            int v = stoi(color.substr(i,2), nullptr, 16);
            int x = (v + 8) / 17; // round to nearest
            if (x < 0) x = 0; if (x > 15) x = 15;
            char c = x < 10 ? '0'+x : 'a'+(x-10);
            res += c; res += c;
        }
        return res;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    public String similarRGB(String color) {
        StringBuilder res = new StringBuilder("#");
        for (int i = 1; i < 7; i += 2) {
            int v = Integer.parseInt(color.substring(i, i+2), 16);
            int x = (v + 8) / 17;
            x = Math.max(0, Math.min(15, x));
            char c = (char)(x < 10 ? '0'+x : 'a'+(x-10));
            res.append(c).append(c);
        }
        return res.toString();
    }
}
1
2
3
4
5
6
7
8
9

class Solution:
    def similarRGB(self, color: str) -> str:
        def closest(x):
            v = int(x, 16)
            d = (v + 8) // 17
            d = max(0, min(15, d))
            c = hex(d)[2:]
            return c*2
        return '#' + ''.join(closest(color[i:i+2]) for i in (1,3,5))

Complexity

  • ⏰ Time complexity: O(1) — Only a few fixed computations.
  • 🧺 Space complexity: O(1) — No extra space used.