Skip to content

791. Custom Sort String 👍

  • Time: $O(|\texttt{order}| + |\texttt{s}|)$
  • Space: $O(26)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
 public:
  string customSortString(string order, string s) {
    string ans;
    vector<int> count(128);

    for (const char c : s)
      ++count[c];

    for (const char c : order)
      while (count[c]-- > 0)
        ans += c;

    for (char c = 'a'; c <= 'z'; ++c)
      while (count[c]-- > 0)
        ans += c;

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
  public String customSortString(final String order, final String s) {
    StringBuilder sb = new StringBuilder();
    int[] count = new int[128];

    for (final char c : s.toCharArray())
      ++count[c];

    for (final char c : order.toCharArray())
      while (count[c]-- > 0)
        sb.append(c);

    for (char c = 'a'; c <= 'z'; ++c)
      while (count[c]-- > 0)
        sb.append(c);

    return sb.toString();
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution:
  def customSortString(self, order: str, s: str) -> str:
    ans = ""
    count = [0] * 26

    for c in s:
      count[ord(c) - ord('a')] += 1

    for c in order:
      while count[ord(c) - ord('a')] > 0:
        ans += c
        count[ord(c) - ord('a')] -= 1

    for c in string.ascii_lowercase:
      for _ in range(count[ord(c) - ord('a')]):
        ans += c

    return ans