# Sort a String According to Another String

Difficulty Level Easy
Sorting StringViews 506

## Problem Statement

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

## Input Format

The first line containing a string s which we need to sort.

Second-line containing a string t which has no duplicates and it has all characters of the string s.

## Output Format

Print the sorted string on the basis of string t.

## Constraints

• 1<=|s|,|t|<=10^6
• s[i] and t[j] must be a lower case character only.

## Example

```abcedabdceade
ebcda```
`eeebbccdddaaa`

Explanation: Here first we count the frequency of each char present in the string s. So, by the above example s = “abcedabdceade” we can easily get that freq of ‘a’ is 3, freq of ‘b’ is 2, freq of ‘c’ is 2, freq of d is 3, and freq of e is 3. So, now we traverse the string t and check the frequency of that char and print it that many times and move to the next char it strings t and repeats the same steps till the end, So, finally we get the sorted string s= “eeebbccdddaaa”.

## Algorithm

1. Store the count of characters of the input string in the freq[] array.
2. Traverse the string t from left to right, for each character t[i], see its count.
3. Print this char that many times.
4. Do this till the end of the pattern string.

## Implementation for Sort a String According to Another String

### C++ program for Sort a String According to Another String

```#include <bits/stdc++.h>
using namespace std;

void SortByPattern(string &s, string t)
{
int freq[26] = {0};
int n=s.length();
int m=t.length();
for(int i=0;i<n;i++)
{
freq[s[i]-'a']++;
}
int index = 0;
for(int i=0;i<m;i++)
{
for(int j=0;j<freq[t[i]-'a'];j++)
{
s[index]=t[i];
index++;
}
}
}

int main()
{
string s,t;
cin>>s>>t;
SortByPattern(s,t);
cout<<s<<endl;
return 0;
}```

### Java Program for Sort a String According to Another String

```import java.util.Arrays;
import java.util.Scanner;

class sum {

static void SortByPattern(String s, String t)
{
int n = s.length();
int m = t.length();
char[] s1 = s.toCharArray();
char[] t1 = t.toCharArray();
int freq[] = new int[26];
Arrays.fill(freq, 0);
for(int i=0;i<n;i++)
{
freq[s1[i]-'a']++;
}
int index=0;
for(int i=0;i<m;i++)
{
for(int j=0;j<freq[t1[i]-'a'];j++)
{
s1[index]=t1[i];
index++;
}
}
for(int i=0;i<n;i++)
{
System.out.print(s1[i]);
}
}
public static void main(String[] args)
{
Scanner sr= new Scanner(System.in);
String s = sr.next();
String t = sr.next();
SortByPattern(s,t);
}
```
```abcabcabc
bxyzca```
`bbbcccaaa`

## Complexity Analysis for Sort a String According to Another String

### Time Complexity

O(N) where N is the size of the given array s. Here we traverse string s that lead us to linear time complexity.

### Space Complexity

O(1) because we don’t use any auxiliary space here.

Translate »