Custom Sort String – LeetCode Solution [Medium]

Problem statement

You are given two strings order and s. All the words of order are unique and were sorted in some custom order previously.

Permute the characters of s 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 s that satisfies this property.

Example

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

Constraints:

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

Also read: https://www.onlycode.in/job-sequencing-problem/ (Greedy approach)

Solution

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

Pseudocode (Greedy Approach)

  • Iterate over string S and order T.
  • Using first come, first serve approach, mark the element in string (S) ‘selected’ (int the order they come), if it comes in order (T) and add the character to the required answer string (ans).
  • After iterating over string S and order T, add the remaining character which were not marked as ‘selected’ to the answer string (ans).

Code

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 s 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:

https://ideone.com/iFYpiV

Leave a Reply

Your email address will not be published.