Skip to main content

791. Custom Sort String

medium

Reorder one string to match the custom alphabet defined by another. A counting-sort variant that highlights why bucket counting beats comparison sorts on bounded alphabets.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

You are given two strings, order and s. All the characters of order are unique and were sorted in some custom order previously. Permute the characters of s so that they match the order that order was sorted. More specifically, if a character x occurs before a character y in order, then x should occur before y in the permuted string. Return any permutation of s that satisfies this property.

Constraints

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

Examples

Example 1

Input
order = "cba", s = "abcd"
Output
"cbad"

Explanation: c, b, a appear in the order given; d (not in order) goes at the end.

Example 2

Input
order = "bcafg", s = "abcd"
Output
"bcad"

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Count each character in s with a frequency table.

Hint 2

Walk order in given sequence; for each character, append it count[c] times to the output and zero out count[c].

Hint 3

Finally append any leftover characters (those not in order) in any order.

Solution approach

Reveal approach

Counting sort. Build freq[c] = count of c in s. Iterate over order: for each c, append c repeated freq[c] times to the output and set freq[c] = 0. Then iterate over the freq table once more and append any remaining counts (characters not in order). O(n + k) time where n = len(s) and k = len(order). O(1) extra space because the frequency table is bounded by the 26-letter alphabet. Building a custom comparator and sorting also works but at O(n log n).

Complexity

Time
O(n + k)
Space
O(1)

Related patterns

  • counting-sort
  • hash-table

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Meta
  • Amazon

Practice these live with InterviewChamp.AI

Drill Custom Sort String and Strings problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →