In this HackerEarth Lexicographically minimal string problem solution You are given three strings named as A, B, and C. Here, the length of the strings A and B is equal. All strings contain lowercase English letters. The string A and B contain the following properties:

  1. The characters located at the same indexes in the string A  and B are equivalent to each other. 
  2. If character a is equivalent to character b, then the character b is also equivalent to the character .
  3. If character a is equivalent to character b and character b is equivalent to character c, then character a is also equivalent to character c.
  4. Every character is equivalent to itself.


HackerEarh Lexicographically minimal string problem solution


HackerEarth Lexicographically minimal string problem solution.

import java.io.IOException;
import java.util.InputMismatchException;
import java.util.Scanner;

public class hacker
{
    static int parent[];
    static int size[];

    public static int find(int i)
    {
        if (parent[i] != i)
        {
            return find(parent[i]);
        }

        return i;
    }

    public static void union(int a, int b)
    {
        int x = find(a);
        int y = find(b);

        if (x != y)
        {
            if (size[x] > size[y])
            {
                size[x] += size[y];
                parent[y] = x;
            } else
            {
                size[y] += size[x];
                parent[x] = y;
            }
        }
    }

    public String solution(String a, String c, String b)
    {
        parent = new int[26];
        size = new int[26];

        for (int i = 0; i < 26; i++)
        {
            parent[i] = i;
        }

        for (int i = 0; i < a.length(); i++)
        {
            int x = (int) (a.charAt(i) - 'a');
            int y = (int) (b.charAt(i) - 'a');
            union(x, y);
        }

        String ans = "";

        for (int i = 0; i < c.length(); i++)
        {
            int f = find((int) (c.charAt(i) - 'a'));

            for (int j = 0; j < 26; j++)
            {
                if (find(j) == f)
                {
                    ans += (char) (j + 'a');
                    break;
                }
            }

        }

        return ans;

    }

    void solve()
    {
        Scanner in = new Scanner(System.in);

        String a = in.nextLine();
        String b = in.nextLine();
        String c = in.nextLine();

        System.out.println(solution(a, c, b));
    }

    void run()
    {

        solve();

    }

    public static void main(String[] args) throws NumberFormatException, InputMismatchException, IOException
    {

        new hacker().run();
    }

}

Second solution

#include<bits/stdc++.h>
using namespace std;
char par[150];
char find(char x)
{
    if(par[x]==x)return par[x];
    return par[x]=find(par[x]);
}
void unionset(char x,char y)
{
    char parx=find(x),pary=find(y);
    if(parx==pary)return;
    if(parx<pary)
        par[pary]=parx;
    else par[parx]=pary;
}
int main()
{
    string a,b,c;
    cin>>a>>b>>c;
    assert(a.size()==b.size());
    for(char i='a';i<='z';i++)
    {
        par[i]=i;
    }
    for(int i=0;i<a.size();i++)
    {
        unionset(a[i],b[i]);
    }
    for(int i=0;i<c.size();i++)
    {
        cout<<find(c[i]);
    }
    cout<<"\n";
    return 0;
}