Sorting is one of the fundamental topics of programming. We have seen different types of sorting algorithms to sort elements based on their value, i.e., either ascending or descending. Still, in this blog, we will see how we can sort a string based on the order of characters present in the given string or, in other words, a custom sort string.
We have been given two strings, ’REFERENCE’ and ‘STR’. All the characters of ‘REFERENCE’ are unique and are sorted in some custom order. Our task is fairly simple we have to sort the string ‘STR’ such that the characters in ‘STR’ match the order in which the characters in the string ’REFERENCE’ are sorted. That is a Custom sort string.
If a character does not occur in ‘REFERENCE’, we can place it anywhere in the string ‘STR’.
Let us understand this better by an example.
‘REFERENCE’ = "fed"
‘S’ = "defx"
Now "d" "e," and "f" appear in 'REFERENCE' string and the order of "d", "e", and "f" is "f", "e", and "d", in 'REFERENCE' thus in our output also order of "d", "e", "f" would be "f", "e", and "d".
Also, as “x” does not occur in any particular order, it can appear anywhere in the returned string. The outputs "xfed", "fxed", and "fedx" are all valid answers
Recommended: Try the Problem yourself before moving on to the solution.
Intuition
The technique that we are going to use here is Bucketing. In bucketing, we usually store the frequency of characters present in the string in a bucket(array).
For example, for the string “codingninjas” the bucket array would look something like this.
Here the first 0th represents the frequency of ‘a’ 1st ‘b’ and so on till ‘z’.
But how is this going to help us in solving our problem?
We will store the frequency of every character of ‘S’ in a bucket array, then we will loop through ‘REFERENCE’ and will check if that character is present in the ‘S’ or not. If it is present, we will add the character in our final string (the number of times it occurs in ‘S’) and will make the frequency of that character zero in the bucket array. Now for the remaining characters, we will run a loop again through ‘S’, check elements whose frequency is not zero, and add them to our final answer string.
Algorithm
Create an array ‘BUCKET_ARRAY’ of size 26 and initialize it to zero.
Loop through ‘STR’ and store frequency of every character of ‘STR’ in ‘BUCKET_ARRAY’ using BUCKET_ARRAY[S[i] - ’a’]++. Here we are using ‘i’ to loop through ‘STR’.
‘FIN_ANS’ will store our final answer.
Loop through ‘REFERENCE’ using ‘i’ and check if the frequency of REFERENCE[i] is greater than 0. If it is greater than 0, then we will add the character to ‘FIN_ANS’ (number of times it occurs in ‘S’), and then we will make it frequency in ‘BUCKET_ARRAY’ zero.
Loop through ‘STR’ for remaining elements which were not present in ‘REFERENCE’ if the frequency of STR[i] is greater than 0. If it is greater than 0, then we will add the character to ‘FIN_ANS’ (number of times it occurs in ‘STR’), and then we will make its frequency in ‘BUCKET_ARRAY’ zero.
Print ‘FIN_ANS’.
Now let us look at the above words in action in the form of code
#include <iostream>
#include <vector>
using namespace std;
string customSortString(string reference, string str)
{
// 'BUCKET_ARRAY' to store the frequency of characters in 'S'.
vector<int> bucketArray(26, 0);
// Storing the frequency of every character in ‘BUCKET_ARRAY’.
for (int i = 0; i < str.length(); i++)
bucketArray[str[i] - 'a']++;
// Final answer would be stored in this string.
string finAns;
// Looping through 'REFERENCE' and adding common characters to our final answer first.
for (int i = 0; i < reference.length(); i++)
{
while (bucketArray[reference[i] - 'a'] >= 1)
{
finAns += reference[i];
bucketArray[reference[i] - 'a']--;
}
}
// Looping through 'STR' and adding character which was not present in 'REFERENCE'.
for (int i = 0; i < str.length(); i++)
{
while (bucketArray[str[i] - 'a'] >= 1)
{
finAns += str[i];
bucketArray[str[i] - 'a']--;
}
}
// Returning the final answer.
return finAns;
}
int main()
{
string reference, str;
// Taking Input.
cin >> reference >> str;
cout << customSortString(reference, str);
return 0;
}
You can also try this code with Online C++ Compiler
O(M + N), where ‘M’ is the length of ‘REFERENCE’ and ‘N’ is the length of ‘STR’.
As we are looping through ‘REFERENCE’ and ‘STR’ once, so the time complexity is O(M)+O(N) = O(M + N).
Space Complexity
The space complexity is O(26). As we are using an array, ‘BUCKETARRAY’ to store the frequency of characters of ‘STR’. As there are 26 characters in the lowercase thus space complexity is O(26).
The array is static in size, whereas the vector is dynamic in size.
What is the time complexity of Merge Sort?
The time complexity of Merge Sort is O(n*log(n)) both in best and worst case time complexity.
Conclusion
Now, you have understood how to custom-sort a string from another string. We saw that this was an application of bucket array and saw how bucket array is implemented. But this is not all, and you should not stop here, so head over to our practice platform Coding Ninjas Studio to practice top problems and many more.
39+ registered 
