# 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(n2).

###### 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