Sort a string by custom order

Given a priority string P of distinct characters and a text string S, reorder S so that all characters appearing in P come first and are grouped in the exact order specified by P, followed by all characters not in P while preserving their original relative order. Return the reordered string. Design an O(|P| + |S|) algorithm and discuss space usage. How would you adapt the solution for Unicode and for case-insensitive ordering?

What a Strong Answer Covers

• A clear algorithm with the right data structures and enough pseudocode or code-level detail to implement it.
• A correctness argument that explains why the algorithm covers all required cases.
• Time and space complexity, plus at least one alternative approach when relevant.
• Focused tests for normal cases, edge cases, and failure modes.

Follow-up Questions

• How would the approach change if the input were streaming or too large for memory?
• What invariants would you assert in production code?
• Which tests would catch off-by-one, duplicate, or tie-breaking bugs?

Sort a String by Custom Order

Given a priority string P of distinct characters and a text string S, reorder S so that:

1. All characters of S that appear in P come first, grouped together in the exact order specified by P (all occurrences of P[0], then all occurrences of P[1], and so on).
2. They are followed by all characters of S that do NOT appear in P, preserving their original relative order from S.

Return the reordered string.

Characters in P are guaranteed distinct. Characters may repeat in S. Aim for an O(|P| + |S|) time algorithm.

Example 1

P = "cba", S = "abcd"
Output: "cbad"

Characters 'a','b','c' all appear in P, so they are ordered as c, b, a. 'd' is not in P, so it comes last.

Example 2

P = "kqep", S = "pekeq"
Output: "kqeep"

Counts: k=1, q=1, e=2, p=1. Emit in P order: k, q, e, e, p.

Example 3

P = "ba", S = "aabbcc"
Output: "bbaacc"

'b' before 'a' per P; 'c' not in P keeps its trailing order.

Constraints

• Characters in P are distinct.
• S may contain repeated characters.
• Either P or S may be empty.
• If P is empty, return S unchanged.
• Characters of S not in P must preserve their original relative order.

Hints

1. Build a hash set (or map) of the characters in P so you can test membership in O(1).
2. Single pass over S: count occurrences of each character that is in P, and append (in order) characters that are not in P to a separate buffer.
3. Emit the result by walking P once and writing each character as many times as it was counted, then append the not-in-P buffer.
4. For Unicode: iterate over code points (Python str already does; in Java/C++ decode UTF-8/UTF-16 to code points) rather than bytes, and key the count map by code point. For case-insensitive ordering, normalize both P and the matched characters with a consistent case fold before comparing, but emit the original characters.

Solution

Solution Alignment

The prompt asks for an implementation-level answer. The safest way to present it is to define the state, maintain clear invariants, then walk through complexity and tests.

Problem Restatement

Given a priority string P of distinct characters and a text string S, reorder S so that all characters appearing in P come first and are grouped in the exact order specified by P, followed by all characters not in P while preserving their original relative order. Return the reordered string. Design an O(|P| + |S|) algorithm and discuss space usage. How would you adapt the solution for Unicode and for case-insensitive ordering?

Recommended Approach

Use the string constraints to choose between two pointers, a stack, frequency counts, prefix/suffix state, or dynamic programming. Maintain the invariant that processed characters have already been normalized, counted, or matched according to the operation.

Correctness

The implementation should maintain an invariant after each loop or operation that directly matches the problem statement. At termination, that invariant implies the returned value has considered every valid candidate exactly once, or has preserved the required data-structure state after every API call.

Complexity

Most direct string scans are O(n) time. Space ranges from O(1) for two pointers to O(n) for stacks, maps, or DP tables.

Edge Cases and Tests

Empty string, length 1, repeated characters, invalid characters, case sensitivity, Unicode vs ASCII, and very long input.