Code Implementation

class Solution:
    def customSortString(self, order: str, s: str) -> str:
        from collections import Counter
        count = Counter(s)
        result = []
        # Add chars in 'order' first
        for c in order:
            if c in count:
                result.append(c * count[c])
                del count[c]
        # Add remaining chars
        for c in count:
            result.append(c * count[c])
        return ''.join(result)
      

class Solution {
public:
    string customSortString(string order, string s) {
        unordered_map<char, int> count;
        for (char c : s) count[c]++;
        string result;
        // Add chars in 'order' first
        for (char c : order) {
            if (count.count(c)) {
                result.append(count[c], c);
                count.erase(c);
            }
        }
        // Add remaining chars
        for (auto &p : count) {
            result.append(p.second, p.first);
        }
        return result;
    }
};
      

class Solution {
    public String customSortString(String order, String s) {
        int[] count = new int[26];
        for (char c : s.toCharArray()) {
            count[c - 'a']++;
        }
        StringBuilder result = new StringBuilder();
        // Add chars in 'order' first
        for (char c : order.toCharArray()) {
            while (count[c - 'a']-- > 0) {
                result.append(c);
            }
        }
        // Add remaining chars
        for (char c = 'a'; c <= 'z'; c++) {
            while (count[c - 'a']-- > 0) {
                result.append(c);
            }
        }
        return result.toString();
    }
}
      

var customSortString = function(order, s) {
    let count = {};
    for (let c of s) {
        count[c] = (count[c] || 0) + 1;
    }
    let result = [];
    // Add chars in 'order' first
    for (let c of order) {
        if (count[c]) {
            result.push(c.repeat(count[c]));
            delete count[c];
        }
    }
    // Add remaining chars
    for (let c in count) {
        result.push(c.repeat(count[c]));
    }
    return result.join('');
};
      

Problem Description

You are given two strings, order and s. The string order is a permutation of distinct lowercase letters, which defines a custom order for the characters. The string s consists of lowercase letters and may contain repeated characters.

Your task is to reorder the characters in s so that they appear in the same relative order as in order. Characters in s that do not appear in order can be placed anywhere after the ordered characters. You must use each character from s exactly as many times as it appears (do not add or remove characters).

• There is always one valid solution.
• Do not reuse or drop any characters from s.
• All characters in order are unique.

Example:
order = "cba", s = "abcd" → Output: "cbad" (or any string where 'c' comes before 'b', and 'b' before 'a', and 'd' can be anywhere at the end).

Thought Process

At first glance, the problem seems to ask for a sort, but with a custom ordering defined by order instead of the usual alphabetical order. For each character in s, we need to determine its position based on order, if it exists there.

The brute-force approach would be to sort s by comparing the index of each character in order. However, this is inefficient because looking up the index in order for every character results in a slow solution, especially when s is long.

To optimize, we can count the occurrences of each character in s, then reconstruct the result by first adding all characters from order (in the right order, as many times as they appear in s), and finally appending the remaining characters that were not in order.

Solution Approach

• Step 1: Count how many times each character appears in s. We use a hash map (dictionary) for this, as lookups and updates are O(1).
• Step 2: Iterate through each character in order. For each character, if it appears in s (i.e., is in our count map), add it to the result as many times as it appears. Remove it from the count map after adding to avoid duplication.
• Step 3: After processing all characters in order, some characters from s may remain (those not in order). Append these to the result in any order, as the problem allows.
• Step 4: Concatenate all collected characters to form the final string.

This approach ensures that:

• All characters from s are used exactly as many times as they appear.
• Characters in order appear first and in the specified order.
• All operations are efficient, leveraging fast hash map lookups.

Example Walkthrough

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

1. Count characters in s:
   • 'a': 1
   • 'b': 1
   • 'c': 1
   • 'd': 1
2. Process order:
   • 'c' is in count: add 'c' once to result. Remove 'c'.
   • 'b' is in count: add 'b' once to result. Remove 'b'.
   • 'a' is in count: add 'a' once to result. Remove 'a'.

   Result so far: "cba"

3. Append remaining characters:
   • Only 'd' is left: add 'd' once to result.

   Final result: "cbad"

The output string has all characters from s, with those in order appearing first and in the prescribed order.

Time and Space Complexity

Brute-Force Approach:

• Sorting s by repeatedly looking up the index of each character in order leads to O(n * m) time, where n is the length of s and m is the length of order.

• Counting characters in s: O(n)
• Processing order: O(m)
• Appending remaining characters: O(n)
• Overall time complexity: O(n + m)
• Space complexity: O(n) for the count map and result string.

This is efficient because both order and s are processed in linear time, and hash map operations are fast.

Summary

The Custom Sort String problem is elegantly solved by counting characters and reconstructing the result based on the custom order. The key insight is to avoid repeated lookups and instead use a hash map for efficient counting and retrieval. This approach guarantees that all characters are placed correctly and efficiently, making the solution both simple and optimal.