Sort a string according to another string

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.

Examples

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

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

Time complexity : O(m+n)

Algorithm

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);
    cout<<str;
    return 0;
}
Try It

 


Next > < Prev
Scroll to Top