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;
}