Home » Technical Interview Questions » String Interview Questions » Sort a string according to another string

Sort a string according to another string

Reading Time - 2 mins

Given two input strings, a pattern and a string. We need to sort the string according to the order defined by pattern. Pattern string has no duplicates and it has all characters of the string.


a) Input string : “code”,pattern: “odec”
Output string : “code”

b) Input string : “ijkh”, pattern: “gfhtukij”
Output string : “huij”

Time complexity : O(m+n)


1. Store the count of characters in the input string.

2. Traverse the pattern string from left to right, for each character pattern[i], see its count.

3. Print it that many times.

4. Do this till the end of pattern string.

C++ Program

#include <bits/stdc++.h>

using namespace std;
void SortByPattern(string &str, string pattern)
    //count array with frequiencies of characters
    int count[26] = {0};
    for (int i = 0 ; i < str.length(); i++)
        count[str[i] - 'a']++;
    //Traverse pattern string and print according to the count array
    int index = 0;
    for (int i = 0; i < pattern.length(); i++)
        for (int j = 0; j < count[pattern[i] - 'a']; j++)
            str[index] = pattern[i];
            index = index + 1;
//Main function
int main()
    string pattern = "odec";
    string str = "code";
    SortByPattern(str, pattern);
    return 0;

Try It


READ  Reverse Bits
Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions