You are given two strings order and s. All the words of order are unique and were sorted in some custom order previously.
Permute the characters of s so that they match the order that order was sorted. More specifically, if a character x occurs before a character y in order, then x should occur before y in the permuted string.
Return any permutation ofsthat satisfies this property.
Input: order ="cba", s ="abcd"Output: "cbad"Explanation:
"a","b","c" appear in order, so the order of "a","b","c" should be "c","b", and "a".Since "d" does not appear in order, it can be at any position in the returned string."dcba","cdba","cbda" are also valid outputs.
To solve this problem we use a counting/bucket approach: count each character in s, then emit characters in the order specified by order, followed by any leftover characters. This is effectively an order-based bucket sort and is optimal for small fixed alphabets.
Create a Mapping: Create a priority map from the custom order string, where each character is assigned an index based on its position in the order string.
Count Characters in s: Count the occurrences of each character in s. This helps in easily constructing the resultant string based on the sorted order.
Construct the Result: Iterate through the order string and add characters to the result based on the count from the previous step. Finally, add any characters from s that were not present in order.
from typing import List
classSolution:
defcustomSortString(self, order: str, s: str) -> str:
count = [0] *26for ch in s:
count[ord(ch) - ord('a')] +=1 ans: List[str] = []
for ch in order:
while count[ord(ch) - ord('a')] >0:
ans.append(ch)
count[ord(ch) - ord('a')] -=1for i in range(26):
ch = chr(ord('a') + i)
while count[i] >0:
ans.append(ch)
count[i] -=1return''.join(ans)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
pubstructSolution;
impl Solution {
pubfncustom_sort_string(order: String, s: String) -> String {
letmut count =vec![0usize; 26];
for b in s.bytes() { count[(b -b'a') asusize] +=1; }
letmut ans = String::new();
for b in order.bytes() {
let idx = (b -b'a') asusize;
for _ in0..count[idx] { ans.push(b aschar); }
count[idx] =0;
}
for i in0..26 {
for _ in0..count[i] { ans.push((b'a'+ i asu8) aschar); }
}
ans
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
functioncustomSortString(order: string, s: string):string {
constcount: number[] =new Array(26).fill(0);
for (constchofs) count[ch.charCodeAt(0) -97]++;
letans='';
for (constchoforder) {
ans+=ch.repeat(count[ch.charCodeAt(0) -97]);
count[ch.charCodeAt(0) -97] =0;
}
for (leti=0; i<26; i++) {
if (count[i] >0) ans+= String.fromCharCode(97+i).repeat(count[i]);
}
returnans;
};
⏰ Time complexity: O(n + m) where n is the length of s and m is the length of order. This includes creating the priority map, counting occurrences, and constructing the result.
🧺 Space complexity: O(n + m) for storing the counts of characters and the resultant string.