Home
Algorithms Data Structures Interview Experiences
Amazon Google Facebook Microsoft Apple Netflix
Play 2048 How to

LeetCode Solutions

791. Custom Sort String

Time: $O(|\texttt{S}| + |\texttt{T}|)$

Space: $O(26)$

			


class Solution {
 public:
  string customSortString(string S, string T) {
    string ans;
    vector<int> count(128);

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

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

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

    return ans;
  }
};




			


class Solution {
  public String customSortString(final String S, final String T) {
    StringBuilder sb = new StringBuilder();
    int[] count = new int[128];

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

    for (final char c : S.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();
  }
}




			


class Solution:
  def customSortString(self, S: str, T: str) -> str:
    ans = ""
    count = [0] * 26

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

    for c in S:
      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