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 Sam K., 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

More Strings practice problems

See all Strings problems →