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:
- The characters located at the same indexes in the string A and B are equivalent to each other.
- If character a is equivalent to character b, then the character b is also equivalent to the character .
- 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.
- Every character is equivalent to itself.
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;
}