< Back




791. Custom Sort String

We're given a string of characters representing the order in which our input string, s, should
conform to. All existing characters matching a character in the order string must be placed in the
same order as the order string. The rest of the characters can be placed in any order.

To solve this, we count the occurrences of each character in the input string. We create a list to
store our result. We iterate over the order string and if the character currently being inspected
matches a character in the input string, we append the character to our result - multiplying the
operation by the counter of the character in the input string.

We wrap up our solution by appending the remaining character not found in the order string.

The solution is as follows:


  from collections import defaultdict, Counter

  class Solution:
      def customSortString(self, order: str, s: str) -> str:
          s_count = Counter(s)
          ans = []

          for c in order:
              if c in s_count:
                  ans += [c] * s_count[c]
                  del s_count[c]

          for c, count in s_count.items():
              ans += [c] * count

          return "".join(ans)


_ Time Complexity:

  O(n) - We iterate through all characters in the input.

_ Space Complexity:

  O(1) - All inputs consist of lowercase English letters, so the space complexity is constant.