Skip to content

800. Similar RGB Color 👎

  • Time: $O(1)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
 public:
  string similarRGB(string color) {
    const vector<string> kShorthands = {"00", "11", "22", "33", "44", "55",
                                        "66", "77", "88", "99", "aa", "bb",
                                        "cc", "dd", "ee", "ff"};
    string ans = "#";

    for (int i = 1; i < color.length(); i += 2) {
      const int currValue = stoi(color.substr(i, 2), 0, 16);
      ans += findClosestShorthand(kShorthands, currValue);
    }

    return ans;
  }

 private:
  static constexpr int maxSimilarity = 255 * 255;

  string findClosestShorthand(const vector<string>& shorthands,
                              int targetValue) {
    string closest = shorthands[0];
    int minSimilarity = maxSimilarity;

    for (const string& shorthand : shorthands) {
      const int shorthandValue = stoi(shorthand, 0, 16);
      const int similarity = pow((targetValue - shorthandValue), 2);
      if (similarity < minSimilarity) {
        closest = shorthand;
        minSimilarity = similarity;
      }
    }

    return closest;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
  public String similarRGB(String color) {
    String[] kShorthands = {"00", "11", "22", "33", "44", "55", "66", "77",
                            "88", "99", "aa", "bb", "cc", "dd", "ee", "ff"};
    StringBuilder ans = new StringBuilder("#");

    for (int i = 1; i < color.length(); i += 2) {
      final int currValue = Integer.parseInt(color.substring(i, i + 2), 16);
      String closestShorthand = findClosestShorthand(currValue, kShorthands);
      ans.append(closestShorthand);
    }

    return ans.toString();
  }

  private static final int maxSimilarity = 255 * 255;

  private String findClosestShorthand(int targetValue, String[] shorthands) {
    String closest = shorthands[0];
    int minSimilarity = Integer.MAX_VALUE;

    for (final String shorthand : shorthands) {
      final int shorthandValue = Integer.parseInt(shorthand, 16);
      final int similarity = (targetValue - shorthandValue) * (targetValue - shorthandValue);
      if (similarity < minSimilarity) {
        closest = shorthand;
        minSimilarity = similarity;
      }
    }

    return closest;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
  def similarRGB(self, color: str) -> str:
    kShorthands = ['00', '11', '22', '33', '44', '55', '66', '77', '88', '99',
                   'aa', 'bb', 'cc', 'dd', 'ee', 'ff']
    ans = ['#']

    for i in range(1, len(color), 2):
      currValue = int(color[i:i + 2], 16)
      closestShorthand = min(kShorthands,
                             key=lambda x: (currValue - int(x, 16))**2)
      ans.append(closestShorthand)

    return ''.join(ans)