Software Development

Lexicographically minimum String possible – GeeksforGeeks


Given three strings, S1, S2, and S3. The characters at the same index in S1 and S2 are considered equivalent and follow the transitive property. For example, if S1 = ‘abc’ and S2 = ‘xcd’, then characters {a, x} are equivalent, and characters {b, c, d} are equivalent, the task is to find and print the lexicographically smallest string that you can obtain from S3 by changing its characters to some other equivalent character obtained from S1 and S2. In other words, you need to replace the characters in S3 with their equivalent characters from S1 and S2 while maintaining the lexicographic order.

Examples:

Input: S1 = “abc” , S2 = “xyz” , S3 =” xazy”
Output: aacb
Explanation: ‘x’ replaced by ‘a’, ‘y’ is replaced by ‘b’ and ‘z’ is replaced by ‘c’

Input: S1 = “abc” , S2 = “xcd” , S3 =” xdc”
Output: abb
Explanation: {a, x} are equivalent, and {b, c, d} are equivalent, so x is replaced with a, d is replaced with b, and c is replaced with b.

Naïve approach: We can solve this problem using the below idea:

  • Create a graph where s1[i] is connected with s2[i].
  • then traverse string s3 from left to right and do the following.
    • Call DFS for the s3[i] node and calculate the minimum character we can reach from node s3[i].
    • assign this minimum character to s3[i].
  • return string s3.

Time Complexity: O(N2)
Auxiliary Space: O ( 1 )

Efficient Approach: We can solve this problem optimally using the below idea:

Idea is to use the DSU {Disjoint Set Union}. We can connect the two characters which are mapped with each other and at the end we traverse the s3 string and assign every s3[i] to the parent of s3[i].

Follow the steps to solve the problem:

  • Make a node for every character.
  • Traverse in the string s1 and do Union of s1[i] with s2[i].
  • When all Union operation is being done.
  • Traverse in the s3 string and for every character of s3[i], assign it to its parent.
  • Return the s3 string.

Below is the C++ implementation of the above idea :

C++

 

#include <bits/stdc++.h>

using namespace std;

 

int parent[1000];

 

int size[1000];

void make(int n)

{

    parent[n] = n;

    size[n] = 1;

}

 

int find(int n)

{

    if (n == parent[n])

        return n;

    return parent[n] = find(parent[n]);

}

 

void Union(int a, int b)

{

    a = find(a);

    b = find(b);

 

    

    

    if (a != b) {

 

        

        

        

        

        if (a > b)

            swap(a, b);

        parent[b] = a;

        size[a] += size[b];

    }

}

 

string solve(string s1, string s2, string s3)

{

 

    

    for (char ch = 'a'; ch <= 'z'; ch++)

        make(ch);

 

    

    for (int i = 0; i < s1.length(); i++) {

        Union(s1[i], s2[i]);

    }

 

    

    

    for (int i = 0; i < s3.length(); i++) {

        s3[i] = find(s3[i]);

    }

 

    

    return s3;

}

 

int main()

{

    string s1, s2, s3;

    s1 = "abc";

    s2 = "xcd";

    s3 = "xdc";

 

    

    cout << solve(s1, s2, s3);

    return 0;

}

Time Complexity: O(N)
Auxiliary Space: O(1), because the number of nodes can never exceed 26 (number of alphabets).

Last Updated :
25 Jul, 2023

Like Article

Save Article