Leetcode 791. Custom Sort String

Let's understand what we're being asked to do. We have two strings: order = 'cba' and s = 'abcd'. We need to reorder s so that characters appearing in order follow that relative sequence.

Tracing through: order says 'c' comes first, then 'b', then 'a'. In s, we have 'a', 'b', 'c', and 'd'. So we must arrange them as: 'c' (highest priority), 'b' (second), 'a' (third), 'd' (not in order, can go anywhere). One valid output: 'cbad'.

Important constraint: Every character from order appears at most once, and all characters are lowercase English letters. Characters in s that don't appear in order can be placed anywhere in the result.

Edge cases to consider: What if s contains characters not in order? (place them anywhere, typically at the end). What if order is empty? What if s has duplicate characters? (preserve all occurrences in the custom order).

Count the frequency of each character in s, then iterate through order and append each character the number of times it appears in s. Finally, append any remaining characters (those not in order) in any order. This approach uses counting rather than comparison-based sorting, making it efficient for the small character set (26 lowercase letters).

def custom_sort_string(order, s):
    """
    Reorder string s to follow custom precedence defined by order.
    Uses character frequency counting (brute force approach).
    """
    # Count frequency of each character in s
    char_count = {}
    for char in s:
        if char in char_count:
            char_count[char] += 1
        else:
            char_count[char] = 1
    
    # Build result by iterating through order
    result = []
    
    # First, append characters that appear in order
    for char in order:
        if char in char_count:
            # Append this character count times
            for _ in range(char_count[char]):
                result.append(char)
            # Mark as processed
            char_count[char] = 0
    
    # Then append remaining characters (not in order)
    for char in s:
        if char in char_count and char_count[char] > 0:
            result.append(char)
            char_count[char] -= 1
    
    # Convert list to string
    return ''.join(result)

Each character in order defines a priority rank. For order = 'cba', character 'c' has rank 0 (highest priority), 'b' has rank 1, 'a' has rank 2.

Characters not in order have no defined priority, so they can be treated as having the lowest priority (or placed arbitrarily).

By assigning each character a numeric priority, we transform a custom ordering problem into a standard sorting problem.

Instead of comparing characters alphabetically ('a' < 'b'), we compare them by their custom priority (priority['c'] < priority['b'] < priority['a']). This makes the solution straightforward: map characters to priorities, then sort.

Think of organizing students by a custom ranking system. If the teacher says 'Charlie first, then Bob, then Alice', you'd assign:

• Charlie: rank 0
• Bob: rank 1
• Alice: rank 2
• Any other students: rank 999 (lowest priority)

Now you can sort the class list by these ranks instead of alphabetically. The mapping from names to ranks is the key insight that makes custom ordering possible.

Create a priority map where each character in order gets a numeric rank (0, 1, 2, ...). Characters not in order get a default low priority (e.g., 26). Convert s to an array, sort it using a custom comparator that compares characters by their priority ranks, then join back into a string. This approach directly applies the custom ordering through comparison-based sorting.

def custom_sort_string(order, s):
    """
    Reorder string s according to custom precedence defined by order.
    Characters in order must appear in s in that relative sequence.
    """
    # Build priority map: each character in order gets a rank (0, 1, 2, ...)
    priority = {}
    for index, char in enumerate(order):
        priority[char] = index
    
    # Characters not in order get default low priority (26)
    # Convert s to list for sorting
    s_list = list(s)
    
    # Sort using custom comparator based on priority ranks
    # Characters with lower priority values come first
    s_list.sort(key=lambda char: priority.get(char, 26))
    
    # Join sorted characters back into string
    result = ''.join(s_list)
    
    return result

• Frequency map + custom ordering pattern: When you need to reorder elements based on custom precedence, use a frequency counter (hash map) to track occurrences, then iterate through the priority order to reconstruct - this decouples counting from ordering and handles both specified and unspecified elements cleanly.
• Two-phase reconstruction technique: Build the result in two passes: first append characters in the order they appear in the priority string (using their frequencies), then append remaining characters not in the priority list - this ensures custom precedence is respected while handling all elements.
• Character frequency as building blocks: Instead of sorting the entire string (O(n log n)), count character frequencies once (O(n)) and use the counts to rebuild the string by appending each character frequency times - this transforms a sorting problem into a counting problem for better performance.
• Hash set for membership testing: Use a set to track which characters have custom ordering so you can efficiently determine (O(1)) which characters to place in the priority phase versus the remainder phase - without this, you'd need O(n) lookups for each character.
• Stable grouping over comparison-based sorting: When custom ordering applies to only a subset of elements, frequency counting + ordered reconstruction (O(n + m)) beats custom comparator sorting (O(n log n)) because you avoid comparing elements that don't need relative ordering.
• Pattern applies to priority-based reordering: This frequency map + priority iteration pattern extends to any problem requiring custom precedence over a subset - think task scheduling with priority queues, rendering layers in specific order, or processing requests with VIP priority while maintaining FIFO for regular users.