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.
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.