LeetCode Problem 791

Difficulty: 🟡 Medium
Topics: Hash Table, String, Sorting

Solution

LeetCode 791, Custom Sort String

Problem Understanding

The problem gives us two strings, order and s.

The string order defines a custom character ordering. Unlike normal alphabetical ordering, the characters in order specify exactly how characters should be prioritized relative to one another. Every character in order is unique, which means there are no conflicts or duplicate priorities.

The string s contains the characters we must rearrange. Our goal is to permute the characters in s so that any characters appearing in order follow the same relative ordering defined by order.

For example, if order = "cba", then:

• 'c' must appear before 'b'
• 'b' must appear before 'a'

Any characters in s that do not appear in order can be placed anywhere in the final string.

The important detail is that the problem only requires relative ordering for characters present in order. Characters outside of order are unrestricted.

The constraints are small:

• order.length <= 26
• s.length <= 200

Since only lowercase English letters are involved, the total possible distinct characters is very limited. This means we can comfortably use hash maps, counting arrays, or even sorting approaches without performance concerns.

Several edge cases are important:

• Characters in s may not exist in order
• s may contain repeated characters
• order may contain characters that never appear in s
• order could contain only one character
• All characters in s could be outside order

The problem guarantees that all characters in order are unique, which simplifies implementation because we never need to resolve conflicting priorities.

Approaches

Brute Force Approach

A straightforward solution is to repeatedly scan s and build the result according to the order specified in order.

We can process each character in order, and for every such character, scan through s to collect all matching occurrences. After that, we perform another pass through s to append characters not present in order.

This works because:

• Characters from order are appended in the correct relative sequence
• Characters not in order are added afterward

However, this approach repeatedly scans the string. If order has length m and s has length n, then the repeated scans lead to O(m * n) time complexity.

Although the constraints are small enough that this would pass, it is not the most efficient or elegant solution.

Optimal Approach

The key insight is that we only care about character frequencies.

Instead of repeatedly scanning s, we can first count how many times each character appears. Then:

1. Iterate through order
2. Append each character as many times as it appears in s
3. Append any remaining characters afterward

This avoids redundant scanning and produces the answer in linear time.

A hash map is ideal here because:

• We need fast frequency lookup
• Characters are used as keys
• Frequency counting is naturally modeled with a dictionary

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(m × n)	O(n)	Repeatedly scans s for each character in order
Optimal	O(m + n)	O(1) or O(k)	Uses frequency counting for direct construction

Here:

• m = len(order)
• n = len(s)
• k is the number of distinct characters, at most 26

Algorithm Walkthrough

Optimal Algorithm

1. Create a frequency map for all characters in s.

We count how many times each character appears because the final string must preserve every occurrence. 2. Initialize an empty result list.

Using a list is more efficient than repeated string concatenation because strings are immutable in Python. 3. Iterate through each character in order.

For every character:

• Check how many times it appears in s
• Append that character to the result exactly that many times
• Remove or reset its count afterward

This guarantees that all ordered characters appear in the correct relative sequence. 4. Iterate through the remaining characters in the frequency map.

These are characters that were not present in order.

Append each remaining character according to its frequency. 5. Join the result list into a string and return it.

Why it works

The algorithm works because every character in order is processed sequentially in the exact required order. Since all occurrences of a character are added before moving to the next ordered character, the relative ordering constraint is satisfied.

Characters not present in order have no restrictions, so appending them afterward still produces a valid answer.

Every character from s is included exactly as many times as it originally appeared, ensuring the result is a valid permutation of s.

Python Solution

from collections import Counter

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

        for char in order:
            if char in frequency:
                result.append(char * frequency[char])
                del frequency[char]

        for char, count in frequency.items():
            result.append(char * count)

        return "".join(result)

The implementation begins by using Counter from Python's collections module to count character frequencies in s.

The result list stores partial string fragments efficiently. Instead of appending characters one by one, the code appends repeated strings such as "c" * 3, which is both simple and efficient.

The first loop processes characters according to the custom order. If a character exists in the frequency map, all its occurrences are appended immediately.

After processing ordered characters, the remaining entries in the frequency map correspond to characters not found in order. Since these characters have no ordering restrictions, they are appended in any order.

Finally, "".join(result) combines all fragments into the final string.

Go Solution

func customSortString(order string, s string) string {
	frequency := make(map[rune]int)

	for _, ch := range s {
		frequency[ch]++
	}

	result := make([]rune, 0)

	for _, ch := range order {
		count, exists := frequency[ch]

		if exists {
			for i := 0; i < count; i++ {
				result = append(result, ch)
			}

			delete(frequency, ch)
		}
	}

	for ch, count := range frequency {
		for i := 0; i < count; i++ {
			result = append(result, ch)
		}
	}

	return string(result)
}

The Go solution follows the same logic as the Python implementation.

A map[rune]int stores character frequencies. Since Go strings are UTF-8 encoded, iterating with range produces rune values safely.

The result is built using a rune slice because repeated string concatenation in Go is inefficient. After construction, the rune slice is converted back into a string.

Unlike Python's Counter, Go requires manual incrementing and explicit deletion from the map.

Worked Examples

Example 1

Input:

order = "cba"
s = "abcd"

Step 1: Build Frequency Map

Character	Count
a	1
b	1
c	1
d	1

Step 2: Process order

Current Character	Action	Result
c	Append "c"	"c"
b	Append "b"	"cb"
a	Append "a"	"cba"

Remaining frequency map:

Character	Count
d	1

Step 3: Append Remaining Characters

Append "d".

Final result:

"cbad"

Example 2

Input:

order = "bcafg"
s = "abcd"

Step 1: Build Frequency Map

Character	Count
a	1
b	1
c	1
d	1

Step 2: Process order

Current Character	Action	Result
b	Append "b"	"b"
c	Append "c"	"bc"
a	Append "a"	"bca"
f	Not present	"bca"
g	Not present	"bca"

Remaining frequency map:

Character	Count
d	1

Step 3: Append Remaining Characters

Append "d".

Final result:

"bcad"

Complexity Analysis

Measure	Complexity	Explanation
Time	O(m + n)	One pass for counting and one pass for construction
Space	O(1) or O(k)	At most 26 lowercase English letters

The algorithm performs a single pass over s to compute frequencies and a single pass over order plus remaining characters to construct the result.

Because the alphabet is limited to lowercase English letters, the auxiliary storage never grows beyond 26 entries, making the effective space complexity constant.

Test Cases

solution = Solution()

# Provided examples
assert solution.customSortString("cba", "abcd") in {
    "cbad", "cbda", "cdba", "dcba"
}  # basic custom ordering

assert solution.customSortString("bcafg", "abcd") in {
    "bcad", "bcda", "dbca"
}  # characters outside order

# Single character order
assert solution.customSortString("a", "aaaa") == "aaaa"  # repeated same character

# Characters not in order
result = solution.customSortString("abc", "xyz")
assert sorted(result) == sorted("xyz")  # no ordered characters

# Mixed ordered and unordered characters
result = solution.customSortString("kqep", "pekeq")
assert result.startswith("kqe") or result.startswith("kqqe")

# Empty ordering effect
result = solution.customSortString("z", "abc")
assert sorted(result) == sorted("abc")  # order irrelevant for all chars

# Duplicate characters
assert solution.customSortString("cba", "aaabbbccc") == "cccbbbaaa"

# Order contains unused characters
result = solution.customSortString("xyzabc", "abccba")
assert result == "aabbcc"

# All characters already in correct order
assert solution.customSortString("abc", "aabbcc") == "aabbcc"

# Reverse ordering
assert solution.customSortString("zyx", "xyzxyz") == "zzyyxx"

Test Summary

Test	Why
"cba", "abcd"	Verifies standard custom ordering
"bcafg", "abcd"	Ensures unordered characters are handled
"a", "aaaa"	Tests repeated identical characters
"abc", "xyz"	Tests case where no characters appear in order
"kqep", "pekeq"	Tests mixed ordering and duplicates
"z", "abc"	Tests minimal order string
"cba", "aaabbbccc"	Tests heavy duplication
"xyzabc", "abccba"	Tests unused order characters
"abc", "aabbcc"	Tests already sorted input
"zyx", "xyzxyz"	Tests reverse custom ordering

Edge Cases

Characters in s Not Present in order

One common source of bugs is forgetting about characters that do not appear in the custom ordering string.

For example:

order = "abc"
s = "abcdxyz"

The problem only constrains the relative order of 'a', 'b', and 'c'. Characters like 'd', 'x', 'y', and 'z' may appear anywhere.

The implementation handles this correctly by leaving those characters in the frequency map after processing order, then appending them afterward.

Duplicate Characters

Another important case is repeated characters.

For example:

order = "cba"
s = "aaabbbccc"

A naive implementation might accidentally append only one occurrence of each character.

The frequency map guarantees correctness because every character is appended exactly according to its stored count.

Order Contains Unused Characters

The order string may include characters that never appear in s.

For example:

order = "xyzabc"
s = "aabbcc"

Characters 'x', 'y', and 'z' are irrelevant because they do not appear in s.

The implementation safely skips them because the frequency map lookup simply fails, resulting in no additions to the result.