{x}
blog image

Custom Sort String

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.

Problem Description

The problem asks to sort the characters of a string s according to the order specified in another string order. Characters in order are unique. If a character x precedes character y in order, then x must precede y in the sorted s. Characters from s not present in order can be placed anywhere in the result.

Solution Approach

Two main approaches are presented:

Approach 1: Sorting with a Custom Key

This approach leverages the built-in sorting functionality of the programming language. We create a dictionary/map to store the index of each character in order. The get method with a default value of 0 handles characters not present in order. The sorting is then done using this index as the key, ensuring the desired order.

Approach 2: Counting and Concatenation

This approach is more efficient in terms of time complexity. We first count the occurrences of each character in s. Then, we iterate through order, adding the corresponding characters to the result string based on their counts. Finally, we add any remaining characters not in order to the end of the string.

Code Implementation and Explanation

The code examples below demonstrate both approaches in several programming languages.

Approach 1: Sorting with a Custom Key

Python3

from collections import Counter
 
class Solution:
    def customSortString(self, order: str, s: str) -> str:
        d = {c: i for i, c in enumerate(order)}  # Create a dictionary mapping characters to their indices in order
        return ''.join(sorted(s, key=lambda x: d.get(x, 0))) # Sort s using the dictionary as a key; characters not in d get index 0

Java

import java.util.*;
import java.util.stream.Collectors;
 
class Solution {
    public String customSortString(String order, String s) {
        int[] d = new int[26]; //array to store indices
        for (int i = 0; i < order.length(); ++i) {
            d[order.charAt(i) - 'a'] = i;  //Store indices
        }
        List<Character> cs = new ArrayList<>(); //Convert string to list for easier sorting
        for (char c : s.toCharArray()) cs.add(c);
        cs.sort((a, b) -> d[a - 'a'] - d[b - 'a']); // Sort using custom comparator based on indices
        return cs.stream().map(String::valueOf).collect(Collectors.joining()); //Convert back to string
    }
}

C++

#include <algorithm>
#include <string>
#include <vector>
 
class Solution {
public:
    string customSortString(string order, string s) {
        int d[26] = {0};  // Array to store indices
        for (int i = 0; i < order.length(); ++i) d[order[i] - 'a'] = i; //Store indices
        sort(s.begin(), s.end(), [&](char a, char b) { return d[a - 'a'] < d[b - 'a']; }); //Sort using lambda expression
        return s;
    }
};

(Other languages are similar; the core idea remains the same: create a mapping and use it as a sorting key.)

Approach 2: Counting and Concatenation

Python3

from collections import Counter
 
class Solution:
    def customSortString(self, order: str, s: str) -> str:
        cnt = Counter(s) # Count character occurrences
        ans = []
        for c in order:
            ans.append(c * cnt[c])  # Add characters from order based on count
            cnt[c] = 0 #Reset count to 0
        for c, v in cnt.items():  # Add remaining characters
            ans.append(c * v)
        return ''.join(ans)

Java

class Solution {
    public String customSortString(String order, String s) {
        int[] cnt = new int[26]; // Array to store counts
        for (char c : s.toCharArray()) ++cnt[c - 'a'];  // Count character occurrences
        StringBuilder ans = new StringBuilder();
        for (char c : order.toCharArray()) {  // Iterate through order
            while (cnt[c - 'a']-- > 0) ans.append(c); //Append characters based on counts
        }
        for (int i = 0; i < 26; ++i) { // Append remaining characters
            while (cnt[i]-- > 0) ans.append((char) ('a' + i));
        }
        return ans.toString();
    }
}

(Other languages are similar; the core idea remains the same: count, then concatenate based on the order string.)

Time and Space Complexity Analysis

Approach 1:

  • Time Complexity: O(N log N), where N is the length of string s. This is dominated by the sorting operation.
  • Space Complexity: O(1). The space used by the dictionary/map is constant because the number of unique characters is at most 26.

Approach 2:

  • Time Complexity: O(M + N), where M is the length of order and N is the length of s. This is because we iterate through order and s once each.
  • Space Complexity: O(1). The space used to store the counts is constant (at most 26 integers).

Approach 2 is generally more efficient due to its linear time complexity compared to the logarithmic time complexity of Approach 1. However, the difference might be negligible for small input sizes.