# Sort a string according to another string

0
83 ## 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 = {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;
}``````