# Lexicographically smallest equivalent string

Moderate
0/80
Average time to solve is 25m
Contributed by

## Problem statement

Ninja has two strings ‘s’ and ‘t’ of same length, he knows that both strings are equivalent strings which means s[i], t[i] will follow all rules of any equivalence relation that are:

• Reflexive : s[i] = t[i]
• Symmetric: s[i] = t[i] => t[i] = s[i]
• Transitive: if s[i] = t[i] and t[i] = s[j] then s[i] = s[j]
• Ninja wants your help to find the lexicographically smallest equivalent string of a given string ‘str’.

Note:

``````1. String ‘s’, ‘t’ and ‘str’ consist of only lowercase English letters from ‘a’ – ‘z’.
2. String ‘s’ and ‘t’ are of same length.
``````

For example:

``````Let s = “abc” , t = “xyz” and str = “xbc” then all strings that we can generate are “abc”, “abz”, “ayc”,”ayz”, “xbc”, “xbz”, “xyc”, “xyz” and smallest of all these is “abc”.
``````
Detailed explanation ( Input/output format, Notes, Images )
Constraints :
``````1 <= T <= 5
1 <= N, M <= 5000

Where ‘T’ is the number of test cases, ‘N’ is the length of string ‘s’ and ‘t’ and ‘M’ is the length of ‘str’.

Time limit: 1 second
``````

#### Sample Input 1:

``````2
coding ninjaa nijng
super aaaaa super
``````

#### Sample Output 1:

``````aiiaa
aaaaa
``````

#### Explanation of Sample Output 1:

``````Test Case 1 : The smallest string that can be formed is:
‘n’ = ‘a’
‘i’ = ‘i’
‘j’ = ‘i’
‘g’ = ’a’
So, “aiiaa”

Test Case 2:  The smallest string that can be formed is:
‘s’ = ‘u’ = ‘p’ = ‘e’ = ‘r’ = ‘a’
So “aaaaa” is shortest string
``````

#### Sample Input 2:

``````2
program awesome wqgmin
abcedf fdecba fanbfa
``````

#### Sample Output 2:

``````aqgain
aanbaa
``````
Console