Sort a String According to Another String

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;
}

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.