⚡Flashcard Drill➔
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

  1. Count the characters of s first.
  2. Walk order and emit each character as many times as it occurs in s, deleting it from the counter as you go.
  3. Whatever remains in the counter consists of characters not in order; emit them in ascending order.
  4. 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 order must 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.
🎯 Drill This Card Now➔

🧩 Related Arrays & Hashing Problems