Custom Sort String – LeetCode Solution [Medium]


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.

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


  • 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)


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 {

    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]) {
                    // marking the character/element in
                    // string T as selected
                    T[j] = 'A';

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

        return ans;

Here’s a working example: Custom Sort String Solution

Leave a Reply

Your email address will not be published. Required fields are marked *