Input to your program are 3 strings S1 S2 and S3 of lower case alphabets and no spaces or special characters. S1 and S2 are the same size. Here are the constraints on S1 and S2:
In string S1 and S2 the alphabets at the same index can be replaced with each other.
If alphabet p can be replaced with q then q can also be replaced with p
If alphabet p can be replaced with alphabet q , and the alphabet q can be replaced with alphabet r then alphabet p can also be replaced with r.
1 < length of strings S1,S2,S3 < 999999
length of string S1 = length of string S2
All the strings consist of lowercase English letters.
Ex : You are given two strings:
S1−pqr
S2−zrg
Here, the alphabet p can be replaced with alphabet z, alphabet q can be replaced with r, and alphabet r with g. The alphabet q can also be replaced with g according to the 3rd rule above.
Input format
First line: String S1
Second line: String S2
Third line: String S3
Output format
You can replace any alphabet of S3 with any of these alternatives based on the properties learned from S1 and S2. By doing so you can construct many such new strings. Out of all these strings your program should output the smallest string assuming they are sorted lexicographically.
Hey @mustaq001
In this problem you can form the groups of character which can replace each other you can maintain this by using DSU or simple brute code and keep the minimum character for each group. After formation of group traverse the string S3 and for each character in string replace it with the minimum character in the group with they belongs.
Making the codebook is fairly straightforward; you just need to step through the two strings and check for each character pair which has the earlier code, then update the other to that value. At the end you should sweep through and update any “stragglers” (that had their code letter updated after getting).
Python routine:
alph = 'abcdefghijklmnopqrstuvwxyz'
def make_codebook(A,B):
# build code book dictionary from these
code = {c:c for c in alph} # initially letters code for themselves
for c1, c2 in zip(A,B):
if code[c1] < code[c2]:
code[c2] = code[c1]
else:
code[c1] = code[c2]
# final reconciliation
for c in alph:
code[c] = code[code[c]]
return code
try out this python code, lets hope this may help you out
def recheck(dp):
flag=0
for i in dp.keys():
if dp[dp[i]] <dp[i]:
dp[i]=dp[dp[i]]
flag+=1
if(flag==0):
return
else:
recheck(dp)
s1=input()
s2=input()
s3=input()
dp={}
for i in range(97,123):
dp[chr(i)]=chr(i)
for i in range(len(s1)):
if(s1[i]<s2[i]):
dp[s2[i]]=s1[i]
elif(s1[i]>s2[i]):
dp[s1[i]]=s2[i]
recheck(dp)
res=""
for i in range(len(s3)):
res+=dp[s3[i]]
print(res)