Limited Time Offer:Up to 25% off Hello Interview Premium

Your Dashboard

Interview Coaching

Mock Interviews

1:1 Mentorship

Salary Negotiation

Practice

Learn

System Design

ML System Design

Low Level Design

Code

Behavioral

Salary Negotiation

Interview Guides

Blog

Community

Interview Questions

Interview Experiences

Peer System Design Library

Ask The Community

Discord

Refer a Friend

Pricing

Become a Coach

⌘K

Pricing Become a Coach

⌘K

Tutor

Get Premium

Leetcode 791. Custom Sort String

Reorder string s to follow the custom precedence defined by string order: every character that appears in order must appear in s in that relative sequence, while characters not in order can be placed anywhere. The task is essentially to apply a custom priority mapping over lowercase letters and produce any permutation of s that respects that precedence.

Asked at:

Meta

DESCRIPTION

Input:

order = "cba", s = "abcd"

Output:

"cbad"

Explanation: Characters 'c', 'b', 'a' from s are reordered according to order. Character 'd' is not in order, so it can be placed at the end.

Constraints:

1 <= order.length <= 26
1 <= s.length <= 200
order and s consist of lowercase English letters only
All characters in order are unique

Understanding the Problem

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).

Brute Force Approach

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).

Visualization

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)

Start custom sort string algorithm

0 / 35

Test Your Knowledge

Complexity Analysis

Time Complexity: O(n + m) We iterate through s once to count frequencies (O(n)), then through order to build the result (O(m)), where n is length of s and m is length of order. Since the character set is fixed at 26, counting operations are O(1).

Space Complexity: O(1) We use a fixed-size frequency array of 26 characters, which is O(1) space regardless of input size.

Building Intuition

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.

Common Mistakes

Forgetting to handle characters in s that don't appear in order - they should be included in the result, typically at the end

Not preserving duplicate characters: if 'a' appears 3 times in s, all 3 occurrences must appear in the result

Using alphabetical comparison instead of custom priority: comparing characters directly ('a' < 'b') instead of their ranks in order

Inefficient priority lookup: repeatedly searching through order string instead of building a hash map once for O(1) lookups

Edge case handling: not considering when order is empty, or when s contains only characters not in order

Optimal Solution

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.

Visualization

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

Start custom sort: reorder s according to order precedence

0 / 9

Test Your Knowledge

Complexity Analysis

Time Complexity: O(n log n) Sorting the string s of length n using a comparison-based sort takes O(n log n) time. Building the priority map takes O(m) where m is length of order, but this is dominated by the sorting step.

Space Complexity: O(n) We need O(n) space to store the array representation of s for sorting, plus O(m) for the priority map (at most 26 entries, so effectively O(1)).

What We've Learned

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.

Test Your Understanding

Why is string the right data structure for this problem?

string provides the optimal access pattern

It's the only data structure that works

It's the easiest to implement

It uses the least memory

Select an answer to see the explanation

Question Timeline

See when this question was last asked and where, including any notes left by other candidates.

Company

Level

Region

Late October, 2025

Meta

Mid-level

Late September, 2025

Meta

Mid-level

Early August, 2025

Meta

Senior

Get Premium to View All 20+ Reports

Comments

Your account is free and you can post anonymously if you choose.

Hello Interview Premium

Recent interview questions

System Design Guided Practice

Exclusive content

Learn More

Leetcode 791. Custom Sort String

DESCRIPTION

Understanding the Problem

Brute Force Approach

Test Your Knowledge

Complexity Analysis

Building Intuition

Common Mistakes

Optimal Solution

Test Your Knowledge

Complexity Analysis

What We've Learned

Related Concepts and Problems to Practice

Test Your Understanding

Question Timeline

Comments

Questions

Learn

Links

Legal

Contact