Practice/Meta/Leetcode 791. Custom Sort String

Leetcode 791. Custom Sort String

CodingMust

Problem

You are given two strings: priority and text. Your task is to rearrange the characters in text such that they follow the ordering defined by priority.

Specifically:

• Characters that appear in priority must maintain their relative order as defined by priority
• Characters that do not appear in priority can be placed anywhere in the result
• All characters from text must appear in the output exactly as many times as they appear in the input

For example, if priority = "bca" and text = "abcd", the output should place all 'b's first, then all 'c's, then all 'a's, and 'd' can go anywhere since it's not in priority.

Requirements

1. Return a string containing all characters from text
2. Characters present in priority must follow the relative order defined by priority
3. Characters not in priority can appear in any position
4. Preserve the frequency of each character from the original text

Constraints

• 1 ≤ priority.length ≤ 26
• 1 ≤ text.length ≤ 200
• Both strings consist of lowercase English letters only
• All characters in priority are unique
• Aim for O(n) time complexity where n is the length of text

Examples

Example 1:

Input: priority = "cba", text = "abcd" Output: "cbad" Explanation: 'c' comes first in priority, then 'b', then 'a'. Character 'd' is not in priority so it can go anywhere.

Example 2:

Input: priority = "xyz", text = "zzyyxx" Output: "xxyyzz" Explanation: All 'x' characters come first (x appears first in priority), then all 'y' characters, then all 'z' characters.

Example 3:

Input: priority = "ace", text = "abcdef" Output: "acebdf" (or "acedbf" or "acebfd", etc.) Explanation: 'a', 'c', 'e' must appear in that order. Characters 'b', 'd', 'f' are not in priority and can be arranged in any order.