Custom Sort String

791.Custom Sort String

String

Hash Table

Counting

Problem Statement:

Given two strings order and s, reorder the characters of s such that they match the order that order defines. Any character that does not appear in order should be placed at the end of the reordered string in any order.

Example:

Input:

order = "cba", s = "abcd"

→

Output:

"cbad"

Algorithm:

1. Count frequencies of characters in T
2. Add characters in S order first
3. Add remaining characters from T
4. Keep track of used characters

Complexity:

Time: O(N + K) where N is length of T, K is length of S | Space: O(1) since max 26 chars

Java Solution:

public String customSortString(String S, String T) {
    // Count frequency of each character in T
    Map<Character, Integer> map = new HashMap<>();
    for (char c : T.toCharArray()) 
        map.put(c, map.getOrDefault(c, 0) + 1);
        
    StringBuilder sb = new StringBuilder();
    
    // First add characters in order of S
    for (char c : S.toCharArray()) 
        if (map.containsKey(c)) 
            addAll(sb, map, c);
    
    // Add remaining characters
    for (char c : map.keySet())
        addAll(sb, map, c);
    
    return sb.toString();
}

public void addAll(StringBuilder sb, Map<Character, Integer> map, char c) {
    // Add character as many times as its frequency
    for (int i = 0; i < map.get(c); i++) 
        sb.append(c);
    map.put(c, 0);  // Mark as used
}

Python Solution:

def customSortString(self, S: str, T: str) -> str:
    # Count frequencies
    counter = Counter(T)
    result = []
    
    # Add characters in order of S
    for c in S:
        if c in counter:
            result.extend([c] * counter[c])
            del counter[c]
    
    # Add remaining characters
    for c, count in counter.items():
        result.extend([c] * count)
        
    return ''.join(result)

C++ Solution:

class Solution {
public:
    string customSortString(string S, string T) {
        unordered_map<char, int> freq;
        // Count frequencies
        for(char c : T) 
            freq[c]++;
        
        string result;
        
        // Add in order of S
        for(char c : S) {
            if(freq.count(c)) {
                result.append(freq[c], c);
                freq.erase(c);
            }
        }
        
        // Add remaining
        for(auto& [c, count] : freq)
            result.append(count, c);
            
        return result;
    }
};