Custom Sort String

Med

#0745Time: O(L + N log N), where L is the length of `order` and N is the length of `s`. Building the rank map takes O(L). Sorting `s` takes O(N log N). Building the final string takes O(N).Space: O(N + L), where L is the length of `order` and N is the length of `s`. We need O(L) space for the rank map (or O(1) for a fixed alphabet) and O(N) space for the character array used for sorting. Given L <= 26, this simplifies to O(N).1 company

Algorithms

Sorting

Data structures

Hash Table String

Companies

Snap

Prompt

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.

Example 1:

Input: order = "cba", s = "abcd"

Output: "cbad"

Explanation: "a", "b", "c" appear in order, so the order of "a", "b", "c" should be "c", "b", and "a".

Since "d" does not appear in order, it can be at any position in the returned string. "dcba", "cdba", "cbda" are also valid outputs.

Example 2:

Input: order = "bcafg", s = "abcd"

Output: "bcad"

Explanation: The characters "b", "c", and "a" from order dictate the order for the characters in s. The character "d" in s does not appear in order, so its position is flexible.

Following the order of appearance in order, "b", "c", and "a" from s should be arranged as "b", "c", "a". "d" can be placed at any position since it's not in order. The output "bcad" correctly follows this rule. Other arrangements like "dbca" or "bcda" would also be valid, as long as "b", "c", "a" maintain their order.

Constraints:

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

Approaches

2 approaches with complexity analysis and trade-offs.

This approach involves defining a custom order for characters based on the order string and then using a standard sorting algorithm to sort the characters of string s. The custom order is established by mapping each character in order to its index. Characters not in order are given a default, higher rank to ensure they appear at the end.

Algorithm

Create an integer array rank of size 26, initialized with a large value (e.g., 27).
Iterate through the order string. For each character c at index i, set rank[c - 'a'] = i.
Convert the input string s into a Character array sChars.
Sort sChars using Arrays.sort and a custom Comparator.
The comparator logic is (c1, c2) -> rank[c1 - 'a'] - rank[c2 - 'a'].
Construct a new string by joining the characters in the sorted array and return it.

Walkthrough

The core idea is to translate the custom sorting problem into a standard sorting problem by providing a custom comparison logic.

First, we create a 'rank' map (an array is efficient for characters) to store the position of each character as defined by the order string. We iterate through order, and for each character c at index i, we set its rank to i. Any character not present in order will have a default rank, typically a value larger than any rank from order, so they are sorted to the end.

Next, we convert the string s into an array of characters, which can be sorted.

We then apply a sorting algorithm (like Arrays.sort) to this array, passing our custom comparator. The comparator uses the pre-computed ranks to decide the order of any two characters.

Finally, the sorted array of characters is converted back into a string.

1import java.util.Arrays;2import java.util.Comparator;3 4class Solution {5    public String customSortString(String order, String s) {6        // Create an array to store the rank of each character.7        int[] rank = new int[26];8        // A large value for characters not in 'order'.9        Arrays.fill(rank, 27); 10        for (int i = 0; i < order.length(); i++) {11            rank[order.charAt(i) - 'a'] = i;12        }13 14        // Convert string 's' to a Character array to sort it.15        Character[] sChars = new Character[s.length()];16        for (int i = 0; i < s.length(); i++) {17            sChars[i] = s.charAt(i);18        }19 20        // Sort the character array using a custom comparator based on rank.21        Arrays.sort(sChars, (c1, c2) -> rank[c1 - 'a'] - rank[c2 - 'a']);22 23        // Build the result string from the sorted character array.24        StringBuilder result = new StringBuilder(sChars.length);25        for (Character c : sChars) {26            result.append(c);27        }28        return result.toString();29    }30}

Complexity

Time

O(L + N log N), where L is the length of `order` and N is the length of `s`. Building the rank map takes O(L). Sorting `s` takes O(N log N). Building the final string takes O(N).

Space

O(N + L), where L is the length of `order` and N is the length of `s`. We need O(L) space for the rank map (or O(1) for a fixed alphabet) and O(N) space for the character array used for sorting. Given L <= 26, this simplifies to O(N).

Trade-offs

Pros

Conceptually straightforward, as it leverages familiar built-in sorting functions.
Relatively easy to implement.

Cons

The time complexity of O(N log N) is not optimal for this problem.
It involves converting the primitive chars of the string to Character objects, which introduces some memory and performance overhead.

This approach uses a frequency map (or a simple array) to count the occurrences of each character in string s. It then constructs the result string by first appending characters in the order specified by the order string, followed by any remaining characters. This avoids a direct comparison-based sort, leading to a more efficient linear time complexity.

Algorithm

Create an integer array counts of size 26 to store the frequency of each character in s.
Iterate through s and populate the counts array.
Initialize an empty StringBuilder to build the result.
Iterate through the order string. For each character c, append it to the StringBuilder counts[c - 'a'] times, then set its count to 0.
Iterate through the counts array from index 0 to 25. For each index i with a non-zero count, append the corresponding character (char)('a' + i) to the StringBuilder that many times.
Return the string from the StringBuilder.

Walkthrough

This method is based on the idea of counting sort, which is highly efficient for data with a small range of keys, like lowercase English letters.

First, we iterate through the string s and count the frequency of each character. An integer array of size 26 is perfect for this, where counts[0] stores the frequency of 'a', counts[1] for 'b', and so on.

Next, we initialize a StringBuilder to build our result. We iterate through the order string. For each character c in order, we look up its count in our frequency array. We append c to our StringBuilder that many times and then reset its count to zero. This ensures that these characters are placed first and in the correct custom order.

Finally, there might be characters in s that were not in order. Their counts in the frequency array are still non-zero. We iterate through our frequency array from 'a' to 'z'. For any character with a remaining count, we append it to the StringBuilder. These characters will appear at the end of the result string, and their relative order will be alphabetical (though any order is acceptable for them).

The final result is obtained by converting the StringBuilder to a string.

1class Solution {2    public String customSortString(String order, String s) {3        // Step 1: Count frequencies of characters in s.4        int[] counts = new int[26];5        for (char c : s.toCharArray()) {6            counts[c - 'a']++;7        }8 9        StringBuilder result = new StringBuilder();10 11        // Step 2: Append characters based on the 'order' string.12        for (char c : order.toCharArray()) {13            while (counts[c - 'a'] > 0) {14                result.append(c);15                counts[c - 'a']--;16            }17        }18 19        // Step 3: Append remaining characters.20        for (int i = 0; i < 26; i++) {21            while (counts[i] > 0) {22                result.append((char) ('a' + i));23                counts[i]--;24            }25        }26 27        return result.toString();28    }29}

Complexity

Time

O(N + L), where N is the length of `s` and L is the length of `order`. It takes O(N) to count frequencies, O(L + N) to build the string based on `order` (total appends are at most N), and O(1 + N) to append the remaining characters.

Space

O(N). We use an O(1) array (size 26) for frequency counts and a `StringBuilder` which requires O(N) space to construct the result string.

Trade-offs

Pros

Highly efficient with a linear time complexity of O(N + L), which is optimal.
Simple to implement and understand, using basic array and string manipulations.

Cons

This specific implementation appends remaining characters in alphabetical order. While valid, if a different order for remaining characters is desired, the final loop would need modification.

Solutions

Solution

1class Solution {2public3  String customSortString(String order, String s) {4    int[] cnt = new int[26];5    for (int i = 0; i < s.length(); ++i) {6      ++cnt[s.charAt(i) - 'a'];7    }8    StringBuilder ans = new StringBuilder();9    for (int i = 0; i < order.length(); ++i) {10      char c = order.charAt(i);11      while (cnt[c - 'a']-- > 0) {12        ans.append(c);13      }14    }15    for (int i = 0; i < 26; ++i) {16      while (cnt[i]-- > 0) {17        ans.append((char)('a' + i));18      }19    }20    return ans.toString();21  }22}

1class Solution {2public:3  string customSortString(string order, string s) {4    int cnt[26] = {0};5    for (char &c : s)6      ++cnt[c - 'a'];7    string ans;8    for (char &c : order)9      while (cnt[c - 'a']-- > 0)10        ans += c;11    for (int i = 0; i < 26; ++i)12      if (cnt[i] > 0)13        ans += string(cnt[i], i + 'a');14    return ans;15  }16};

1class Solution:2    def customSortString(self, order: str, s: str) -> str: cnt = Counter(s) ans = [] for c in order: ans . append(c * cnt[c]) cnt[c] = 0 for c, v in cnt . items(): ans . append(c * v) return '' . join(ans)

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem