Mutating counts without cleanup
Wrong move: Zero-count keys stay in map and break distinct/count constraints.
Usually fails on: Window/map size checks are consistently off by one.
Fix: Delete keys when count reaches zero.
Move from brute-force thinking to an efficient approach using hash map strategy.
You are given two strings order and s. All the characters 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 of s that satisfies this property.
Example 1:
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.
Example 2:
Input: order = "bcafg", s = "abcd"
Output: "bcad"
Explanation: The characters "b", "c", and "a" from order dictate the order for the characters in s. The character "d" in s does not appear in order, so its position is flexible.
Following the order of appearance in order, "b", "c", and "a" from s should be arranged as "b", "c", "a". "d" can be placed at any position since it's not in order. The output "bcad" correctly follows this rule. Other arrangements like "dbca" or "bcda" would also be valid, as long as "b", "c", "a" maintain their order.
Constraints:
1 <= order.length <= 261 <= s.length <= 200order and s consist of lowercase English letters.order are unique.Problem summary: You are given two strings order and s. All the characters 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 of s that satisfies this property.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Hash Map
"cba" "abcd"
"bcafg" "abcd"
sort-the-students-by-their-kth-score)Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #791: Custom Sort String
class Solution {
public String customSortString(String order, String s) {
int[] d = new int[26];
for (int i = 0; i < order.length(); ++i) {
d[order.charAt(i) - 'a'] = i;
}
List<Character> cs = new ArrayList<>();
for (int i = 0; i < s.length(); ++i) {
cs.add(s.charAt(i));
}
cs.sort((a, b) -> d[a - 'a'] - d[b - 'a']);
return cs.stream().map(String::valueOf).collect(Collectors.joining());
}
}
// Accepted solution for LeetCode #791: Custom Sort String
func customSortString(order string, s string) string {
d := [26]int{}
for i := range order {
d[order[i]-'a'] = i
}
cs := []byte(s)
sort.Slice(cs, func(i, j int) bool { return d[cs[i]-'a'] < d[cs[j]-'a'] })
return string(cs)
}
# Accepted solution for LeetCode #791: Custom Sort String
class Solution:
def customSortString(self, order: str, s: str) -> str:
d = {c: i for i, c in enumerate(order)}
return ''.join(sorted(s, key=lambda x: d.get(x, 0)))
// Accepted solution for LeetCode #791: Custom Sort String
impl Solution {
pub fn custom_sort_string(order: String, s: String) -> String {
let n = order.len();
let mut d = [n; 26];
for (i, c) in order.as_bytes().iter().enumerate() {
d[(c - b'a') as usize] = i;
}
let mut ans = s.chars().collect::<Vec<_>>();
ans.sort_by(|&a, &b| {
d[((a as u8) - ('a' as u8)) as usize].cmp(&d[((b as u8) - ('a' as u8)) as usize])
});
ans.into_iter().collect()
}
}
// Accepted solution for LeetCode #791: Custom Sort String
function customSortString(order: string, s: string): string {
const toIndex = (c: string) => c.charCodeAt(0) - 'a'.charCodeAt(0);
const n = order.length;
const d = new Array(26).fill(n);
for (let i = 0; i < n; i++) {
d[toIndex(order[i])] = i;
}
return [...s].sort((a, b) => d[toIndex(a)] - d[toIndex(b)]).join('');
}
Use this to step through a reusable interview workflow for this problem.
For each element, scan the rest of the array looking for a match. Two nested loops give n × (n−1)/2 comparisons = O(n²). No extra space since we only use loop indices.
One pass through the input, performing O(1) hash map lookups and insertions at each step. The hash map may store up to n entries in the worst case. This is the classic space-for-time tradeoff: O(n) extra memory eliminates an inner loop.
Review these before coding to avoid predictable interview regressions.
Wrong move: Zero-count keys stay in map and break distinct/count constraints.
Usually fails on: Window/map size checks are consistently off by one.
Fix: Delete keys when count reaches zero.