Morgan and a String – HackerRank Solution

In this post, we will solve Morgan and a String HackerRank Solution. This problem (Morgan and a String) is a part of HackerRank Problem Solving series.

Contents

Solution – Morgan and a String – HackerRank Solution

C++

#include <iostream>
using namespace std;

int main() {
    int T;
    for(cin >> T; T > 0; T--) {
        string A, B, result;
        cin >> A >> B;
        result.reserve(A.size() + B.size() + 1);
        for(auto i = 0, j = 0; i < A.size() || j < B.size(); ) {
            auto k = i, l = j;
            while(k < A.size() && l < B.size() && A[k] == B[l]) {
                k++;
                l++;
            }
            if(k == A.size()) {
                for(l = j; j < B.size() && B[j] == B[l]; j++) {
                    result.push_back(B[j]);
                }
            } else if(l == B.size()) {
                for(k = i; i < A.size() && A[i] == A[k]; i++) {
                    result.push_back(A[i]);
                }
            } else if(A[k] < B[l]) {
                for(k = i; i < A.size() && A[i] == A[k]; i++) {
                    result.push_back(A[i]);
                }
            } else {
                for(l = j; j < B.size() && B[j] == B[l]; j++) {
                    result.push_back(B[j]);
                }
            }
        }
        result.push_back('\n');
        cout << result;
    }
    return 0;
}

Python

T = int(input())

def alpha_min(a, b):
    la = len(a)
    lb = len(b)
    a += "z"
    b += "z"
    i = j = 0
    res = ""
    while (i != la and j != lb):
        if a[i:] < b[j:]:
            res += a[i]
            i += 1
        else:
            res += b[j]
            j += 1
        
    res += a[i: -1] + b[j: -1]
    return res
    
for _ in range(T):
    
    a = input().strip()
    b = input().strip()
    print(alpha_min(a, b))

Java

import java.io.*;
import java.util.*;

public class Solution {

    public static void main(String[] args) {
        
        Scanner input = new Scanner(System.in);
        int t = input.nextInt();
        
        for(int a0 = 0; a0 < t; a0++)
        {
            StringBuilder s1 = new StringBuilder(input.next()); s1.append("z");//Denote end
            StringBuilder s2 = new StringBuilder(input.next()); s2.append("z");//Denote end
            StringBuilder output = new StringBuilder("");
            
            int i = 0, j = 0;//Index into each string
            while(i < s1.length() && j < s2.length())
            {
                ////////////Simple cases/////////////
                if(s1.charAt(i) < s2.charAt(j))
                {
                    output.append(s1.charAt(i));
                    i++;
                }
                else if(s1.charAt(i) > s2.charAt(j))
                {
                    output.append(s2.charAt(j));
                    j++;
                }
                //////////////////////////////////////
                
                
                
                ///////Characters are different///////
                else 
                {
                    if(s1.charAt(i) == 'z'){i++; j++; continue;}//End has been reached

                    
                    int startingI = i;
                    int startingJ = j;
                    
                    //Find the point at which their equality diverges
                    while(s1.charAt(i) == s2.charAt(j))
                    {
                        i++;
                        j++;
                        if(i >= s1.length() && j >= s2.length()) //They are the same string
                        {
                            i = startingI;
                            j = startingJ;
                            break;  
                        }
                        else if(i >= s1.length()) //String 1 is shorter than string 2
                        {
                            //We append all chars that are in a decreasing sequence 
                            ////////ex: gdbad would return gdba
                            char prev = s2.charAt(startingJ);
                            while(s2.charAt(startingJ) <= prev)
                            {
                                output.append(s2.charAt(startingJ));
                                prev = s2.charAt(startingJ);
                                startingI++;
                            }
                            i = startingI;
                            j = startingJ;
                        }
                        else if(j >= s2.length()) //String 2 is shorter than string 1
                        {
                            char prev = s1.charAt(startingI);
                            while(s1.charAt(startingI) <= prev)
                            {
                                output.append(s1.charAt(startingI));
                                prev = s1.charAt(startingI);
                                startingI++;
                            }
                            i = startingI;
                            j = startingJ;
                        }
                    }
                    
                    
                    //They are different strings
                    
                    //String 1 is lexicographically smaller than String 2
                    if(s1.charAt(i) <= s2.charAt(j))
                    {
                        char prev = s1.charAt(startingI);
                        while(s1.charAt(startingI) <= prev)
                        {
                            output.append(s1.charAt(startingI));
                            prev = s1.charAt(startingI);
                            startingI++;
                        }
                        i = startingI;
                        j = startingJ;
                    }
                    
                    //String 2 is lexicographically smaller than String 1
                    if(s1.charAt(i) > s2.charAt(j))
                    {
                        char prev = s2.charAt(startingJ);
                        while(s2.charAt(startingJ) <= prev)
                        {
                            output.append(s2.charAt(startingJ));
                            prev = s2.charAt(startingJ);
                            startingJ++;
                        }
                        i = startingI;
                        j = startingJ;
                    }
                }
            }
            
            
            //We reached the end of 1 string
            //Add rest of string 1
            while(i < s1.length())
            {
                output.append(s1.charAt(i));
                i++;
            } 
            
            //Add rest of string 2
            while(j < s2.length())
            {
                output.append(s2.charAt(j));
                j++;
            }
            
            
            //Print the output
            System.out.println(output);
        }
    }
}

Note: This problem (Morgan and a String) is generated by HackerRank but the solution is provided by CodingBroz. This tutorial is only for Educational and Learning purpose.

Leave a Comment

Your email address will not be published. Required fields are marked *