Sorting a string using another sorting order string [closed]

Question

I saw this in an interview question , Given a sorting order string, you are asked to sort the input string based on the given sorting order string.
for example if the sorting order string is dfbcae and the Input string is abcdeeabc the output should be dbbccaaee.

any ideas on how to do this , in an efficient way ?

Answer 1

The Counting Sort option is pretty cool, and fast when the string to be sorted is long compared to the sort order string.

• create an array where each index corresponds to a letter in the alphabet, this is the count array
• for each letter in the sort target, increment the index in the count array which corresponds to that letter
• for each letter in the sort order string
  • add that letter to the end of the output string a number of times equal to it's count in the count array

Algorithmic complexity is O(n) where n is the length of the string to be sorted. As the Wikipedia article explains we're able to beat the lower bound on standard comparison based sorting because this isn't a comparison based sort.

Here's some pseudocode.

char[26] countArray;
foreach(char c in sortTarget)
{
    countArray[c - 'a']++;
}

int head = 0;
foreach(char c in sortOrder)
{
    while(countArray[c - 'a'] > 0)
    {
        sortTarget[head] = c;
        head++;
        countArray[c - 'a']--;
    }
}

Note: this implementation requires that both strings contain only lowercase characters.