Last Updated: 4 Apr, 2021

Lexicographically smallest equivalent string

Moderate

Asked in companies

Solve now

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

Input Format:

The first line of input contains an integer 'T' representing the number of test cases.

The first and the only line of each test case contains three space-separated strings ‘s’, ‘t’ and ‘str’.

Output Format :

For each test case, print a single line containing a single string denoting the smallest equivalent string of ‘str’.

The output for 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 <= 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

Solve now

Approaches

01 Approach

The idea here is to use disjoint set union or union-find data structure.

It provides the following capabilities. We are given several elements, each of which is a separate set. A DSU will have an operation to combine any two sets, and it will be able to tell in which set a specific element is.

Thus the basic interface of this data structure consists of only three operations:

union_sets(a, b) - merges the two specified sets (the set in which the element a is located, and the set in which the element b is located), as we need the lexicographically smallest element as root so we will add one more condition while union two sets.
find_set(v) - returns the representative (also called leader) of the set that contains the element v. This representative is an element of its corresponding set. It is selected in each set by the data structure itself (and can change over time, namely after union_sets calls). This representative can be used to check if two elements are part of the same set or not. a and b are exactly in the same set, if find_set(a) == find_set(b). Otherwise, they are in different sets.

We iterate both string ‘s’ and ‘t’ and union all characters placed at the same index i.e.

union(s[i],t[i]) where i goes from 0 -> s.length-1.

And to make the lexicographically smallest string we just return the find_set value of each character of ‘str’.

Algorithm:

Declare an array parent of size 26 and initialize it with its index value.
for( i : 0 -> s.length )
- union_set(s[i],t[i])
Declare an empty string res = “”
for(i : 0 -> str.length )
- res += find_set( str[i] )
return res

Description of union_set(int a, int b)

first find representation of each set
- a = find_set(a)
- b = find_set(b)
If ( a != b )
- if( a < b )
  - Parent[b] = a.
Else
- Parent[a] = b

Description of find_set(int v)

if( v == parent[v] ) return v.
return parent[v] = find_set(v)

Solve now