791. Custom Sort String

The Custom Sort String problem is a classic coding interview question because it tests whether you can follow a custom ordering rule instead of relying on default sorting. Interviewers use it to see how you handle real constraints like duplicates in s and extra characters that aren’t mentioned in order.

Problem statement

You are given two lowercase strings: order, which lists some characters in a special “preferred” ordering (with no repeats), and s, which contains characters you can rearrange. Your task is to permute s so that any characters that appear in order show up in s following the same relative ordering as in order.

The tricky part is that s can contain repeated characters and also characters not mentioned in order. Those “unspecified” characters are allowed anywhere, so you must enforce the custom ordering only for the subset of characters controlled by order while still returning a valid permutation of the entire s.

Constraints:

• 1 <= order.length <= 26
• 1 <= s.length <= 200
• order and s consists of lowercase English letters.
• All characters of order are unique.

Examples

Naive approach: Trying all permutations

One straightforward idea is to generate permutations of s and return the first one that satisfies the ordering rule. But s can be up to length 200, and the number of permutations grows astronomically. Even if you try to “sort” s by comparing characters using order, doing it with repeated lookups and custom comparisons can still be clumsy and easy to get wrong with duplicates.

A better way is to avoid re-checking the relative order repeatedly. Instead, we should build the result directly from character frequencies, so each character is placed exactly as many times as it appears, with no wasted work.

Optimized approach: Custom Order via Frequency Count

A better way to solve this problem is to count how many times each character appears in s. Then, output characters in the exact sequence specified by order, repeating each as many times as its frequency. After that, append all remaining characters (those not present in order) in any order, again based on their frequencies.

This works cleanly even with repeated characters because we never compare individual positions or try to “move” letters around; we simply emit the correct number of each character in a valid sequence.

Why does this work even with unconstrained characters

Characters not in order do not participate in any required relative ordering, so they can appear anywhere without breaking the rule. By appending them after all constrained characters, we automatically satisfy the constraint, while still using every character from s exactly once.

Solution steps

1. Count characters in s by building a frequency map counts where counts[c] = how many times character c appears in s.
2. Create an empty list out to collect pieces of the final string efficiently.
3. For each character ch in order:
   1. If ch exists in counts:
      1. Append ch repeated counts[ch] times to out.
      2. Remove ch from counts (so it won’t be added again later).
4. Append remaining characters (not in order). For each (ch, cnt) still left in counts:
   1. Append ch repeated cnt times to out (Their relative order doesn’t matter.).
5. Join all parts in out into one string and return it.

Take a look at the illustration below to understand the solution more clearly.

1 / 10

Solution implementation

from collections import Counter

def customSortString(order, s):
    counts = Counter(s)
    out = []

    # Emit characters that are controlled by `order`, in that exact order.
    for ch in order:
        if ch in counts:
            out.append(ch * counts[ch])
            del counts[ch]

    # Emit all remaining characters (not present in `order`) in any order.
    for ch, cnt in counts.items():
        out.append(ch * cnt)

    return "".join(out)
    
def main():
    orders = ["cba", "cbafg", "kqep", "hucw", "a"]
    strings = ["abcd", "abcdafgabc", "pekeq", "utzochhcu", "aaaaa"]

    for i in range(len(orders)):
        print("Test case:", i+1)
        print("\torder: ", orders[i])
        print("\ts: ", strings[i])
        print("\n\tResult:", customSortString(orders[i], strings[i]))
        print("-"*75)

if __name__ == "__main__":
    main()

Time complexity

The time complexity is O(n + m) where n is the length of s and m is the length of order. Counting characters in s takes linear time, and building the output touches each character count a constant number of times overall.

Space complexity

The space complexity is O(1) in terms of alphabet size because the frequency map stores at most 26 lowercase letters. The output itself requires O(n) space to build the permuted string.

Edge cases

• s contains no characters from order
  • Example: order = "abc", s = "ddd"
  • Why the solution handles it: the ordered loop appends nothing, and all characters remain in the leftover map and get appended normally.
• order includes characters not present in s
  • Example: order = "xyz", s = "aabb"
  • Why the solution handles it: missing characters simply don’t appear in the frequency map and are skipped.
• s has many duplicates of ordered characters
  • Example: order = "cba", s = "aaabbbccccd"
  • Why the solution handles it: counts ensure each ordered character group is emitted fully and in the correct group order.
• Smallest inputs
  • Example: order = "a", s = "a"
  • Why the solution handles it: counts are correct and the loops still produce the right result.

Common pitfalls

• Trying to “sort” with a comparator without defining how to rank characters not in order
  • This often leads to bugs or inconsistent placement of characters that don’t appear in order.
• Forgetting about duplicates
  • Placing each character once based on order and ignoring frequency will produce a string missing characters.
• Not removing processed characters from the count map
  • This can accidentally output ordered characters twice: once in the order loop and again in leftovers.
• Assuming the remaining characters must keep their original order
  • The problem allows any permutation; forcing stability can complicate your solution unnecessarily.