Custom Sort String – LeetCode Solution [Medium]

Problem

You are given two strings order and t. All the words of order are unique and were sorted in some custom order previously.
Permute the characters of t so that they match the order that order was sorted. More specifically, if a character x occurs before a character y in order, then x should occur before y in the permuted string.

Return any permutation of string t that satisfies this property.

Example

Input: order = "cbafg", t = "abcd"
Output: "cbad"

Constraints:

• 1 <= order.length <= 26
• 1 <= t.length <= 200
• order and t consist of lowercase English letters.
• All the characters of order are unique.

Also read: Job Sequencing Problem (Greedy approach)

Solution

This problem has very loose constraints. So we could use a naive solution with time complexity O(n²).

Pseudocode (Greedy Approach)

• Iterate over order S (order string) and string T.
• Using first come, first serve approach, mark the character x as selected, whenever it comes in string T in the order they come in order string S and add it to the required string (ans).
  For example, if S = ‘abc’ and T = ‘baa’ then in the 1st iteration, we’ll mark the character ‘a’ (since a occurs first in order string (S)) in T as selected and add ‘a’ & ‘a’ to the ans string. So, string T and ans will become, T = “bAA”, ans = “aa”, where ‘A’ signifies T[1] and T[2] as selected and already added to the ans.
• After iterating over string S and order T, add the remaining character of string T which were not marked as ‘selected’ to the answer string (ans).

Code Implementation

class Solution {
public:

    string customSortString(string S, string T) {

        string ans = "";

        for (int i=0; i<S.size(); i++) {
            for (int j=0; j<T.size(); j++) {
                if (T[j] == S[i]) {
                    ans.push_back(S[i]);
                    // marking the character/element in
                    // string T as selected
                    T[j] = 'A';
                }
            }
        }

        for (int i=0; i<T.size(); i++) {
            if (T[i] != 'A') {
                ans.push_back(T[i]);
            }
        }

        return ans;
    }
};

Here’s a working example: Custom Sort String Solution