Does anybody know how to solve this lexicographical algorithm

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.

Sample Input
dcba
edcb
decb

Output
aaaa

hey bro did u find the both ans please reply me with the code asap would be gret help

Hey @mustaq001 :wave:
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.

That’s a great idea @amiytiwari_adm , I would like to try this in my eclipse IDE

plz send me the code of this problem,

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
1 Like

bro how do i get the exact output from it as it shown in the problem …reply me if you read this

what error are you getting? Can you share it!!

This post was flagged by the community and is temporarily hidden.

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)

Used list of set to find the answer:

public static String process(String s1, String s2, String s3){
        List<TreeSet<Character>> neighbourPool = new ArrayList<>();
        neighbourPool.add(new TreeSet<>());
        neighbourPool.get(0).add(s1.charAt(0));
        neighbourPool.get(0).add(s2.charAt(0));
        for(int i=1;i<s1.length();i++){
            int contains = -1;
            for(int j=0;j<neighbourPool.size();j++){

                if((neighbourPool.get(j).contains(s1.charAt(i)) || neighbourPool.get(j).contains(s2.charAt(i))) && (contains==-1)){
                    neighbourPool.get(j).add(s1.charAt(i));
                    neighbourPool.get(j).add(s2.charAt(i));
                    contains = j;
                } else if((neighbourPool.get(j).contains(s1.charAt(i)) || neighbourPool.get(j).contains(s2.charAt(i))) && (contains!=-1)){
                    Iterator itr = neighbourPool.get(j).iterator();
                    while(itr.hasNext()){
                        Character data = (Character)itr.next();
                        neighbourPool.get(contains).add(data);
                        neighbourPool.get(j).remove(data);
                        itr = neighbourPool.get(j).iterator();
                    }
                }
            }

            if(contains == -1){
                neighbourPool.add(new TreeSet<>());

                neighbourPool.get(neighbourPool.size()-1).add(s1.charAt(i));
                neighbourPool.get(neighbourPool.size()-1).add(s2.charAt(i));
            }
        }

        System.out.println(neighbourPool);
        
        String result = "";

        boolean flag = false;

        for(int i=0;i<s3.length();i++){
            flag = false;
            for(int j=0;j<neighbourPool.size();j++){
                if(neighbourPool.get(j).contains(s3.charAt(i))){
                    result += Character.toString(neighbourPool.get(j).first());
                    flag = true;
                    break;
                }
            }
            if(!flag){
                result += Character.toString(s3.charAt(i));
            }
        }

        return result;

    }