Custom Sort String

Easy

0/40

Average time to solve is 10m

13 upvotes

Asked in companies

Problem statement

You are provided with the two strings named X and Y respectively. Y has its own specific order and has no repeating characters. Your task is to arrange the characters of the first string i.e. X in such a way that the order of characters in X is exactly the same as in Y, which means if ‘d’ occurs after ‘c’ in Y then it should also occur after ‘c’ in X ( obviously if X has ‘d’ and ‘c’ as characters in it ). All you have to do is, convert string X in the specific order with respect to string Y.

Note :

Both the strings have only lowercase English alphabets. 
There may be more than one correct solution, you have to return any one of the possible solutions.

Detailed explanation ( Input/output format, Notes, Images )

Input format:

The first line of input contains an integer ‘T’ denoting the number of test cases.

Then the T test cases follow.

The first line of each test case contains the string X.
The second line of each test case contains the string Y.

Output format:

For each test case, print the string X after converting string X in the specific order with respect to string Y.

The output of each test case is printed in a separate line.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints :

1 <= T <= 10
1 <= |X| <= 10000
1 <= |Y| <= 26
where ‘T’ is the number of test cases, |X| is the length of the first string and |Y| is the length of the second string.
Time Limit: 1 sec

Sample Input 1:

1
acabd
abc

Sample Output 1:

aabcd

Explanation of Sample Input 1:

String Y has ‘a’ first then ‘b’ and then ‘c’ and therefore string X must be ordered as ‘aabcd’ to keep the respective order of characters same as in string Y.
Other possible answers are: ‘daabc’ , ‘adabc’ , ‘aadbc’, ‘aabdc’.

Sample Input 2:

4
dfhfgk
h
aabbb
gd
abababab
ab
cag
abcdef

Sample Output 2:

hdffgk
aabbb
aaaabbbb
acg

Hint 1

Follow the order of characters in Y.

Approaches (1)

Approach 1

Brute Force

The idea is to follow the order in which the characters occur in string Y. We have to run two nested loops on strings Y and X respectively and if Yi is the same as Xj then pick this character and add it to the answer string.
For the remaining characters of X that are not in the string Y, we have to just add those characters in our answer string. To find those remaining characters we can create a vector of visited characters or a hash set.

Time Complexity

O(N), where N is the length of string X.

For every character of string Y, every character of string X is visited. And, string Y can have at most 26 characters. Thus the above step takes O(26*N) time (N is the length of string X). Moreover, a hash table is created which can have a size of 26 in the worst case, assuming all its operations take constant time. We are also iterating over the string X at the end.
Thus the final time complexity will be O(26*N) + O(1) + O(N), that is, O(N).

Space Complexity

O(1)

We are creating the visited vector or a hash set but it will only be storing at most 26 characters in the worst case. Thus, the space complexity will be O(1).

(100% EXP penalty)

Custom Sort String

Console