Custom Sort String — Editorial

Opening the reading…

Intuitionwhy counting is enough to rebuild the required permutation

The required result is determined by two facts: each character must appear exactly as many times as it appears in s, and characters mentioned in order must appear in that sequence. You do not need to compare pairs of characters or decide where each occurrence goes individually. Count the available copies first, then consume those counts in the order required by order.

After processing order, any counts left belong to characters that order never mentioned. Those characters have no relative restriction, so appending them in alphabetic order is valid. The count array acts like a set of buckets: every append removes one character from its bucket, which guarantees that the output neither loses nor invents occurrences.

Approachconsume constrained characters first, then drain the leftovers

Create a count for each lowercase letter and scan s to fill it, because the output must preserve every occurrence and a single count records all copies of a character.

Create an empty answer string, because characters must be appended in their final order rather than rearranged repeatedly after insertion.

Scan order from left to right and append the current character while its count is positive, because this places every constrained character before all later characters in order and consumes exactly its available copies.

Scan all 26 letter buckets and append every remaining copy, because characters absent from order can appear anywhere but must still be included in the result.

Return the answer after both passes, because the first pass handles the required custom sequence and the second pass handles every unconstrained character.

Complexitythe alphabet is fixed at 26 lowercase letters

MEASURE	BOUND	WHY
Time	O(n + m)	The first scan counts each character of s once, the order scan processes each character of order once, and the final scan checks 26 fixed buckets while each remaining occurrence is appended exactly once.
Space	O(1) extra	The count array always has 26 entries, regardless of n or m. The returned string is required output and is excluded from the extra-space bound.

Here n is the length of s and m is the length of order. The alphabet size is fixed at 26.

Annotated solutionC++ · counting buckets · complete judge-ready implementation

CPPCount each letter, consume order from left to right, then append every leftover character.

#include <string>
using namespace std;

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

        string ans;
        for (char c : order) {
            while (cnt[c - 'a']-- > 0) {
                ans.push_back(c);
            }
        }

        for (int i = 0; i < 26; i++) {
            while (cnt[i]-- > 0) {
                ans.push_back('a' + i);
            }
        }

        return ans;
    }
};

The condition in each while loop is deliberately tied to decrementing the count. A bucket with count 3 appends its character three times and ends at -1 after the failed condition check, but it can never append a fourth copy. By the time the final alphabet scan begins, every character mentioned in order has been fully consumed, so only unconstrained characters remain.