Question
Merge Two Strings
You are given two strings a and b. You need to merge them into a new string c.
At each step:
-
You may choose the first character of either
aorb. -
The chosen character is appended to
c. -
That character is then removed from its original string.
Repeat this process until both a and b are empty.
Your task is to construct the lexicographically smallest possible merged string c.
Input
First line contains string a.
Second line contains string b.
Second line contains string b.
Output
Print the lexicographically smallest possible merged string c.
Example
Input:
acdb
bdca
Output:
abcdbdca
Explanation:
At every step, we compare the remaining parts of both strings and pick the smaller one’s first character. Following this rule step by step produces the merged string abcdbdca.
acdb
bdca
Output:
abcdbdca
Explanation:
At every step, we compare the remaining parts of both strings and pick the smaller one’s first character. Following this rule step by step produces the merged string abcdbdca.