Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding
Ninjas X Naukri.com

Last Updated: 4 Apr, 2021

Moderate

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

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

```
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’.
```

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

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

```
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
```

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.

- if( a < b )
- Else
- Parent[a] = b

Description of find_set(int v)

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

Similar problems

Group Points

Hard

Posted: 3 Sep, 2021

Group Points

Hard

Posted: 3 Sep, 2021

Group Points

Hard

Posted: 3 Sep, 2021

Check Equations

Moderate

Posted: 8 Nov, 2021

Ninja And The Malicious Software

Hard

Posted: 29 Nov, 2021

Ninja And The Malicious Software

Hard

Posted: 29 Nov, 2021

Ninja And The Malicious Software

Hard

Posted: 29 Nov, 2021

Ninja And The Malicious Software

Hard

Posted: 29 Nov, 2021

Good Bad Graph

Hard

Posted: 26 May, 2022

Good Bad Graph

Hard

Posted: 26 May, 2022

COUNT ISLANDS

Moderate

Posted: 14 Sep, 2022