Sort a String According to Another String  

Difficulty Level Easy
Frequently asked in Accenture Accolite Adobe Amazon FreeCharge InfoEdge Microsoft Salesforce
Sorting 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.

Please click Like if you loved this article?

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”.

See also
Longest Substring Without Repeating Characters

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.

Please click Like if you loved this article?

Ads Blocker Image Powered by Code Help Pro
Ads Blocker Detected!!!

This website does not work properly with AdBlock. We have detected that you are using extensions to block ads. Please disable Adblocker to view the content.

Refresh