In this HackerRank Morgan and a String problem solution, we have given a lexicographically minimal string made of two collections and we need to take a letter from a collection only when it is on the top of the stack and we need to use all of the letters in the collections and form a new collection.
Problem solution in 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))
Problem solution in Java.
import java.util.Scanner; public class Solution { public static void main(String[] args) { Scanner in = new Scanner(System.in); int t = in.nextInt(); in.nextLine(); while(t-- > 0) { String A = in.nextLine(); String B = in.nextLine(); int i = 0, j = 0; StringBuffer sb = new StringBuffer(); while(i < A.length() && j < B.length()) { if (A.charAt(i) < B.charAt(j)) { sb.append(A.charAt(i++)); } else if (A.charAt(i) > B.charAt(j)) { sb.append(B.charAt(j++)); } else { int x = i, y = j; char a = A.charAt(i); for(; x < A.length() && y < B.length(); x++, y++) { if (A.charAt(x) != B.charAt(y)) { break; } else if (A.charAt(x) > a) { sb.append(A.substring(i, x)).append(B.substring(j, y)); i = x; j = y; a = A.charAt(x); } } if (x == A.length()) { sb.append(B.charAt(j)); j++; } else if (y == B.length()) { sb.append(A.charAt(i)); i++; } else { if (A.charAt(x) < B.charAt(y)) { sb.append(A.charAt(i)); i++; } else { sb.append(B.charAt(j)); j++; } } } } sb.append(A.substring(i)).append(B.substring(j)); System.out.println(sb); } } }
Problem solution in C++.
#include <cmath> #include <cstdio> #include <vector> #include <iostream> #include <algorithm> using namespace std; int main() { /* Enter your code here. Read input from STDIN. Print output to STDOUT */ int t; cin >> t; string s1, s2, o; while(t--) { cin >> s1 >> s2; int l1 = s1.length(); int l2 = s2.length(); int p1 = 0, p2 = 0; o = ""; while(p1 < l1 && p2 < l2) { while(p1 < l1 && p2 < l2 && s1[p1] != s2[p2]) { if(s1[p1] < s2[p2]) o += s1[p1++]; else o += s2[p2++]; } int c = 0, e = 0; while(p1+c < l1 && p2+c < l2 && s1[p1+c] == s2[p2+c] && s1[p1+c] == s1[p1]) { ++e; ++c; } while(p1+c < l1 && p2+c < l2 && s1[p1+c] == s2[p2+c] && s1[p1+c] <= s1[p1]) ++c; if(p1+c < l1 && p2+c < l2) if(s1[p1+c] < s2[p2+c]) while(e--) o += s1[p1++]; else while(e--) o += s2[p2++]; else if(p1+c == l1) while(e--) o += s2[p2++]; else if(p2+c == l2) while(e--) o += s1[p1++]; } while(p1 < l1) o += s1[p1++]; while(p2 < l2) o += s2[p2++]; cout << o << endl; } return 0; }
Problem solution in C.
#include <stdio.h> #include <string.h> #include <math.h> #include <stdlib.h> char str1[100002] = {0}; char str2[100002] = {0}; int main() { /* Enter your code here. Read input from STDIN. Print output to STDOUT */ int t; scanf("%d", &t); while(t--){ scanf("%s", str1); scanf("%s", str2); int len1 = strlen(str1); int len2 = strlen(str2); str1[len1++] = 'z'; str2[len2++] = 'z'; str1[len1] = ' '; str2[len2] = ' '; int i = 0, j = 0; while(str1[i] != 'z' || str2[j] != 'z'){ if(str1[i] < str2[j]){ printf("%c",str1[i]); i++; }else if(str1[i] > str2[j]){ printf("%c", str2[j]); j++; }else{ int res = strcmp(str1 + i +1, str2 + j + 1); if(res <= 0) { printf("%c", str1[i]); i++; }else{ printf("%c", str2[j]); j++; } } } printf("n"); } return 0; }