Custom Sort String

Problem Statement

In the given problem, you are provided with two strings: order and s. The string order contains unique characters that have been pre-sorted according to a custom lexicographical order. Your task is to rearrange the characters in the string s such that they follow the same custom order defined by order. Notably, any character in s that does not appear in order can be placed in any position in the result string. The primary requirement is to maintain the relative order of characters that are present in order when arranging s.

Examples

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 <= 26
• 1 <= s.length <= 200
• order and s consist of lowercase English letters.
• All the characters of order are unique.

Approach and Intuition

When tackling this problem, our goal is to respect the predefined character sequence in order while rearranging s. Here's a step-by-step approach to solving this:

1. Count Characters in s:
   Start by counting how many times each character appears in s. This can be efficiently done using a hash map or an array of size 26 (since the problem constraints guarantee only lowercase English letters).

2. Initialize Result:
   Prepare to build the resulting string by considering characters in the order specified by order.

3. Construct Ordered Part:
   Iterate over each character in order. For each character, if it's present in s (i.e., its count in our map/array is greater than 0), append it to the result string as many times as it appears in s. Reduce the count in the map/array accordingly.

4. Add Remaining Characters:
   After constructing the part of the result string that is governed by order, you will add the characters not present in order. These characters can appear in any order, so simply append them to the result string in any sequence (or the sequence they originally appear in s).

This approach ensures that every character from s that appears in the order string is positioned according to the specified custom order, while characters not referenced by order follow afterward. The time complexity primarily involves traversing through the strings order and s, making this method efficient and fitting well within the provided constraints.

Solutions

class Solution {
    public:
    string sortAccordingToPattern(string pattern, string inputStr) {
        // Frequency counter for characters in inputStr
        unordered_map<char, int> frequencyMap;

        // Count frequencies of elements in inputStr
        for (char ch : inputStr) {
            frequencyMap[ch]++;
        }

        // Generate the output string based on pattern
        string sortedString = "";
        for (char ch : pattern) {
            while (frequencyMap[ch]-- > 0) {
                sortedString += ch;
            }
        }

        // Append characters not in pattern to the sortedString
        for (auto & p : frequencyMap) {
            while (p.second-- > 0) {
                sortedString += p.first;
            }
        }

        // Return finalized sorted string
        return sortedString;
    }
};

class Solution {
    public String sortCustomOrder(String orderPattern, String str) {
        Map<Character, Integer> charFrequency = new HashMap<>();

        int strLength = str.length();
        for (int i = 0; i < strLength; i++) {
            char ch = str.charAt(i);
            charFrequency.put(ch, charFrequency.getOrDefault(ch, 0) + 1);
        }

        StringBuilder sortedString = new StringBuilder();
        int orderLength = orderPattern.length();
        for (int i = 0; i < orderLength; i++) {
            char ch = orderPattern.charAt(i);
            while (charFrequency.getOrDefault(ch, 0) > 0) {
                sortedString.append(ch);
                charFrequency.put(ch, charFrequency.get(ch) - 1);
            }
        }

        for (char ch : charFrequency.keySet()) {
            int count = charFrequency.get(ch);
            while (count > 0) {
                sortedString.append(ch);
                count--;
            }
        }

        return sortedString.toString();
    }
}