Solving Morgan and a String Challenge

4

We will see in this article how to solve the famous Morgan and a String challenge.

The challenge

Jack and Daniel are friends. Both of them like letters, especially upper-case ones. 
They are cutting upper-case letters from newspapers, and each one of them has his collection of letters stored in a stack.

One beautiful day, Morgan visited Jack and Daniel. He saw their collections. He wondered what is the lexicographically minimal string made of those two collections. He can take a letter from a collection only when it is on the top of the stack. Morgan wants to use all of the letters in their collections.

Example

As an example, assume Jack has collected a = [A, C, A]
and Daniel has b = [B, C, F].
The example shows the top at index for each stack of letters. Assembling the string would go as follows:

Jack Daniel Result
ACA BCF
CA BCF A
CA CF AB
A CF ABC
A CF ABCA
  F ABCAC
    ABCACF

Input

The first line contains an integer which is the number of tests, we will call this n.
The next n lines are structured as follows: the first line contains the first string, and the second line contains the second string.

Output

We will print the lexicographically minimal string found for each test case.

Function Example

Input

2
JACK
DANIEL
ABACABA
ABACABA

Output

DAJACKNIEL
AABABACABACABA

Explanation

The first letters to choose from were J and D since they were at the top of the stack. D was chosen, the options then were J and A. A chosen. Then the two stacks have J and N, so J is chosen. (Current string is DAJ) Continuing this way till the end gives us the resulting string.

Solution

First let’s start by creating the boilerplate of our class with the imports which we will use later, and with the first input reader (which is n).

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;

public class MorganString {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        /* Reading the number of tests */
        int n = in.nextInt();
        in.nextLine();
    }
}

Now we must iterate over all the test cases using the variable n and read the inputs of the two lines (we will call them A and B).
We just need to add the following while block (you’re free to use any loop block).

while (n-- > 0) 
  String A = in.nextLine();
  String B = in.nextLine();
}

We will iterate over A and B to determine the first letter to add and then append it to a StringBuffer which will store the result.
We will use two variables to i and j to iterate over these strings, and a string buffer called sb

int i = 0;
int j = 0;
StringBuffer sb = new StringBuffer();
while(i < A.length() && j < B.length()) {

}

Now will test each character of A and B.

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++));
}

If these conditions are not met, we have to iterate over the remaining character  to determine which ones we need to add to our result string sb.
We start by the positions of i and j, and then we move forward and compare each character simultanly. 

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);
   }
}

Now if we reach the end of one of these strings, we add the character from the unfinished one.

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++;
}

Now we append the last characters of each string.

sb.append(A.substring(i)).append(B.substring(j));

All we have to do now is print out the string containing the result, which in our case is sb.

System.out.println(sb);

That’s one of the many solutions for the Morgan and a String problem.

Complete Code

import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.regex.*;

public class MorganString {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        int n = in.nextInt();
        in.nextLine();

        while(n-- > 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);
        }
    }
}

 

Related Posts

Leave a Reply