Custom Sort String

medium strings sorting hashing

Problem

Given an order string with unique characters and a string s, permute the characters of s so that they follow the relative order in order. Characters not in order may appear anywhere. Return any such permutation.

Inputorder = "cba", s = "abcd"

Output"cbad"

c, b, a appear in order; d (not in order) can go anywhere.

order, s (comma-separated)

from collections import Counter

def customSortString(order, s):
    cnt = Counter(s)
    out = []
    for c in order:
        if c in cnt:
            out.append(c * cnt[c])
            del cnt[c]
    for c, k in cnt.items():
        out.append(c * k)
    return ''.join(out)

var customSortString = function(order, s) {
    const cnt = {};
    for (const c of s) cnt[c] = (cnt[c] || 0) + 1;
    let out = '';
    for (const c of order) {
        if (cnt[c]) { out += c.repeat(cnt[c]); delete cnt[c]; }
    }
    for (const c in cnt) out += c.repeat(cnt[c]);
    return out;
};

class Solution {
    public String customSortString(String order, String s) {
        int[] cnt = new int[26];
        for (char c : s.toCharArray()) cnt[c - 'a']++;
        StringBuilder sb = new StringBuilder();
        for (char c : order.toCharArray()) {
            while (cnt[c - 'a']-- > 0) sb.append(c);
        }
        for (char c = 'a'; c <= 'z'; c++)
            while (cnt[c - 'a']-- > 0) sb.append(c);
        return sb.toString();
    }
}

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

Explanation

We need to rearrange s so its letters follow the order given by order, with any leftover letters allowed anywhere. The neat shortcut is that we never really "sort" — we just count letters and emit them in the right order.

First we build a frequency map cnt of every character in s. This tells us how many of each letter we have to place.

Then we walk through order. For each character c that appears in s, we append it cnt[c] times in a block and remove it from the map. Because we process order left to right, the output automatically respects the required relative order.

Finally, whatever is still left in cnt are characters not mentioned in order. The rules say they can go anywhere, so we simply append them at the end.

Example: order="cba", s="abcd". Counts are c:1, b:1, a:1, d:1. Walking order emits c, b, a; then the leftover d is tacked on, giving "cbad".

Time: O(n + m) Space: O(1)