Skip to main content

Custom Sort String

Problem Descriptionโ€‹

You are given two strings order and s. All the characters 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.

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

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 "bacd" 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.

Solution for Custom Sort Stringโ€‹

Approach 1: Custom Comparatorโ€‹

Intuitionโ€‹

A comparator is a tool used to define (or redefine) an order between two items of the same class or data type. Most languages allow for the use of a custom comparator. This means that we can define a rule that determines how an array is sorted, and leverage built-in sort functions for custom sort.

Recall that a comparator takes two values c1 and c2 as parameters and returns the following:

  1. If c1 comes before c2, return a negative integer.
  2. If c1 comes after c2, return a positive integer.
  3. If c1 and c2 are equal, return 000. Letter c1 should come before c2 in the sorted order of s if and only if the index of c1 in the order string is less than the index of c2. By evaluating c1 and c2 as integer indices, we can use subtraction to achieve a return value that abides by the three rules described above.

Let's consider the following example: let s = "bdadeec" and order = "edcba". Letter "e" is at index 0 in order, whereas letter "b" is at index 3. Because 0<30 < 3, "e" should come before "b" in the result string. Therefore, the return result is 0โˆ’3=โˆ’30 - 3 = -3, a negative number that adheres to the first rule listed above.

Taking into account all possible relationships between pairs of letters, the result string is "eeddcba".

Algorithmโ€‹

  1. Create a character array of input string s to allow modification.
  2. Use the built-in sort method and define the comparator function as the difference between the index of c1 and the index of c2 in order.
  3. Concatenate the character array into a string.
  4. Return this resulting string.

Code in Different Languagesโ€‹

Written by @Shreyash3087
class Solution {
public:
string customSortString(string order, string s) {
// Define the custom comparator as lambda
sort(s.begin(), s.end(), [order](char c1, char c2) {
return order.find(c1) < order.find(c2);
});
return s;
}
};

Complexity Analysisโ€‹

Time Complexity: O(NlogN)O(NlogN)โ€‹

Reason: Sorting an array of length N requires O(NlogโกN)O(NlogโกN) time, and the indices of order have to be retrieved for each distinct letter, which results in an O(NlogโกN+K)O(NlogโกN+K) complexity. K is at most 26, the number of unique English letters, so we can simplify the time complexity to O(NlogโกN)O(NlogโกN).

Space Complexity: O(N)O(N)โ€‹

Reason: The space complexity of the sorting algorithm depends on the programming language.

  • In Java, Arrays.sort() is implemented using a variant of the Quick Sort algorithm, which has a space complexity of O(logโกN)O(logโกN) for sorting two arrays. The Java solution also uses an auxiliary array of length N. This is the dominating term for the Java solution.
  • In C++, the sort() function is implemented as a hybrid of Quick Sort, Heap Sort, and Insertion Sort, with a worse-case space complexity of O(logโกโกN)O(logโกโกN). This is the main space used by the C++ solution.

Approach 2: Frequency Table and Countingโ€‹

Intuitionโ€‹

Because the order string already gives us the explicit ordering to sort all the letters, we can generate a sorted version of s without calling upon an O(NlogโกN)O(NlogโกN) algorithm. Let's create a frequency table where the key equals a character c, and the value equals how many times c appears in the string s. Then, for each character in order, append the number of occurrences of that character in s to the resulting string. After iterating through order, any remaining characters in s can be appended to the end without disrupting the defined sorting order.

Algorithmโ€‹

  1. Initialize a frequency table (here we use a Hashmap, but a frequency array works too).
  2. Populate the frequency table by incrementing freq[letter] for each letter in s.
  3. For each character of order, append to result the same frequency it appears in s.
  4. Iterate through the frequency table to find any remaining letters of s not in order, and append these letters to result.
  5. Return the resulting string.

Code in Different Languagesโ€‹

Written by @Shreyash3087
class Solution {
public:
string customSortString(string order, string s) {
// Create a frequency table
unordered_map<char, int> freq;

// Initialize frequencies of letters
// freq[c] = frequency of char c in s
for (char letter : s) {
freq[letter]++;
}

// Iterate order string to append to result
string result = "";
for (char letter : order) {
while (freq[letter]-- > 0) {
result += letter;
}
}

// Iterate through freq and append remaining letters
// This is necessary because some letters may not appear in `order`
for (auto & [letter, count] : freq) {
while (count-- > 0) {
result += letter;
}
}

// Return the result
return result;
}
};

Complexity Analysisโ€‹

Time Complexity: O(N)O(N)โ€‹

Reason: It takes O(N)O(N) time to populate the frequency table, and all other hashmap operations performed take O(1)O(1) time in the average case. Building the result string also takes O(N)O(N) time because each letter from s is appended to the result in the custom order, making the overall time complexity O(N)O(N).

Space Complexity: O(N)O(N)โ€‹

Reason: A hash map and a result string are created, which results in an additional space complexity of O(N)O(N).

Video Solutionโ€‹

Referencesโ€‹


Authors:

Loading...