Custom Sort String

Custom Sort String

What is this problem about?

The Custom Sort String interview question asks you to sort a string s based on a custom character priority defined by another string order. All characters in order are unique and define the new "alphabetical" sequence. If a character in s is not present in order, its position relative to others doesn't matter, though it should still be included in the output.

Why is this asked in interviews?

Companies like Meta and Snap use this string interview pattern to test your ability to use frequency maps and custom sorting logic. It evaluates if you can solve the problem in O(N+M) time using a counting approach, rather than O(N log N) using a general-purpose sort. It's a practical problem that mirrors tasks like ordering data based on user-defined preferences.

Algorithmic pattern used

This problem is best solved using Frequency Counting (Bucket Sort concept).

1. Count the frequency of each character in the string s using a Hash Map or an array of size 26.
2. Iterate through the characters in the order string.
3. For each character, append it to the result string as many times as it appeared in s.
4. Decrease its count in the frequency map to zero.
5. Finally, iterate through the frequency map and append all remaining characters (those that were not in order) to the result.

Example explanation

order = "cba", s = "abcd"

1. Frequencies of s: {a: 1, b: 1, c: 1, d: 1}.
2. Follow order:
   • 'c': appears 1 time. Result = "c".
   • 'b': appears 1 time. Result = "cb".
   • 'a': appears 1 time. Result = "cba".
3. Remaining characters in s:
   • 'd': appears 1 time. Result = "cbad". Output: "cbad".

Common mistakes candidates make

• Using a General Sort: Using a custom comparator with a standard sort() function. While correct (O(N log N)), it's less efficient than the counting approach (O(N)).
• Missing Characters: Forgetting to include the characters from s that were not present in the order string.
• String Immutability: Repeatedly concatenating strings in a loop in languages like Java or C#, which leads to O(N^2) complexity. Use StringBuilder or character arrays instead.

Interview preparation tip

Whenever you need to sort based on a fixed alphabet (like the 26 lowercase letters), Counting Sort is almost always the most efficient way to go.