Custom Sort String

How it works

Instead of sorting, we can build the result string directly by counting character frequencies. Since we know the desired order of characters, we first iterate through order and append each character as many times as it appears in s. Then we handle any remaining characters not in order by iterating through the alphabet. This avoids the O(n log n) sorting overhead.

Steps

1. Create a frequency array of size 26 to count occurrences of each character in s.
2. Iterate through each character in order. For each character, append it to the result as many times as its count, then set its count to 0.
3. Iterate through all 26 letters. Append any remaining characters (those not in order) to the result based on their counts.
4. Return the constructed result string.

Complexity

• Time complexity: O(n)
• Space complexity: O(n)

Things to watch for

Dropping Characters Not Present in Order

Characters in s that do not appear in order must still be included in the result. Forgetting to append these leftover characters produces an incomplete output.

Using Unstable Sort and Expecting Relative Order Preservation

When using a comparison-based sort, characters with the same rank (those not in order) may have their relative order changed. While technically valid per the problem, this can cause confusion. Using a counting approach avoids this issue entirely.

Incorrect Rank Assignment for Missing Characters

Characters not in order need a default rank higher than any position in order. Forgetting to assign a default or using a rank that conflicts with valid positions causes incorrect sorting.

class Solution:
    def customSortString(self, order: str, s: str) -> str:
        count = [0] * 26
        for c in s:
            count[ord(c) - ord('a')] += 1

        res = []
        for c in order:
            idx = ord(c) - ord('a')
            while count[idx]:
                res.append(c)
                count[idx] -= 1

        for idx in range(26):
            c = chr(ord('a') + idx)
            while count[idx]:
                count[idx] -= 1
                res.append(c)

        return ''.join(res)

class Solution {
public:
    string customSortString(string order, string s) {
        vector<int> count(26, 0);
        for (char c : s) {
            count[c - 'a']++;
        }

        string res;
        for (char c : order) {
            int idx = c - 'a';
            while (count[idx] > 0) {
                res += c;
                count[idx]--;
            }
        }

        for (int idx = 0; idx < 26; ++idx) {
            char c = 'a' + idx;
            while (count[idx] > 0) {
                res += c;
                count[idx]--;
            }
        }

        return res;
    }
};