Lexicographically smallest equivalent string

Moderate
0/80
Average time to solve is 25m
profile
Contributed by
18 upvotes
Asked in companies
MicrosoftPayPal

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 )

    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

    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
    Hint

    Try to use union-find to merge the strings by prefix and get the lexicographically smallest equivalent string.

    Approaches (1)
    DSU

    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)
    Time Complexity

    O(N + M), where ‘N’ is the length of string ’s’ and ‘t’ and ‘M’ is the length of string ‘str’.

     

    We are iterating both strings, and storing in a DSU takes O(1) because total characters are 26 only.

    Space Complexity

    O(1).

     

    We are storing a single array parent of constant size 26.

    Code Solution
    (100% EXP penalty)
    Lexicographically smallest equivalent string
    Full screen
    Console