NeetCode #97LC-791MediumArrays & Hashing
← Back to All Problems#97 · #791 · Custom Sort String(自定义字符串排序)
📌 Problem Statement & Constraints
You are given two strings
order and s. Reorder s so that its characters follow order's ordering; characters not in order are placed at the end in ascending order. Constraints: 1 <= order.length <= 26, 1 <= s.length <= 200; order and s consist of lowercase letters, and order has distinct characters.💡 Core Algorithmic Approaches
- Count the characters of
sfirst. - Walk
orderand emit each character as many times as it occurs ins, deleting it from the counter as you go. - Whatever remains in the counter consists of characters not in
order; emit them in ascending order. - This is a stable counting sort with a custom alphabet -- O(n + k) rather than a comparison sort.
💻 Benchmark Python3 Implementation
class Solution:
def customSortString(self, order: str, s: str) -> str:
from collections import Counter
cnt = Counter(s)
res = []
for ch in order:
if ch in cnt:
res.append(ch * cnt[ch])
del cnt[ch]
for ch in sorted(cnt): # leftovers, ascending
res.append(ch * cnt[ch])
return "".join(res)⚡ Complexity Deep Dive
⏱️ Time Complexity
O(|s| + |order| + V log V): counting is linear, and the leftover sort is over at most 26 characters.
💾 Space Complexity
O(k) for the counter, k <= 26.
⚠️ Interview Pitfalls & Follow-ups
- Forgetting the leftovers: characters absent from
ordermust still appear in the output, in ascending order. - Emitting each character once instead of
cnt[ch]times: the multiplicities must be preserved. - Using a comparison sort with a custom comparator: O(n log n) and much more code than the counting approach.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.