Last Updated: 21 Apr, 2021
Largest Merge Of Two Strings
Moderate
Asked in company
You are given two strings, ‘STR1’ and ‘STR2’. Your task is to construct the lexicographically largest string by merging ‘STR1’ and ‘STR2’. While merging the strings, you need to keep the same order of characters in the merged string as present in ‘STR1’ and ‘STR2’.
For example:
Consider STR1 = ”ca” and STR2 = ”db”. All the possible strings that can be constructed by merging “ca” and “db” are “cadb”, “cdab”, “cdba”, “dcab”, “dcba” and “dbca”, among them the lexicographically largest string is “dcba”. Hence, the answer is “dcba” in this case.
Input Format:
The first line of the input contains an integer, 'T,’ denoting the number of test cases.
The first line of each test case contains the string ‘STR1’.
The second line of each test case contains the string ‘STR2’.
Output Format:
For each test case, print a single line containing a single string denoting the lexicographically largest string constructed by merging ‘STR1’ and ‘STR2’.
The output of each test case will be printed in a separate line.
Note:
You don’t need to print anything. It has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 10
1 <= |STR1| <= 3000
1 <= |STR2| <= 3000
Strings 'STR1' and 'STR2' contain lowercase English letters only.
Where 'T' denotes the number of test cases, ‘STR1’ and ‘STR2’ represent the two given strings.
Time limit: 1 sec.
Approaches
The idea is to use a recursive approach to find the lexicographically largest string constructed by merging both strings. We will merge STR1 and STR2 character by character. The recursive idea is clear that there are only two choices, either to choose the next character from the string STR1 or the string STR2 for any character in the merged string. Using this idea, we can construct the lexicographically largest string recursively.
We will define a function largestMergedString(STR1, STR2) to find the lexicographically largest merge of both strings. At each recursive call, we will find the next character to be included in the merged string. The next character should be from the lexicographically larger string between STR1 and STR2. Our approach will be to find the lexicographically greater string and includes its first character in the merged string.
Working of the Recursive function:
- If STR1 is empty, then we will return STR2. Similarly, If STR2 is empty, then we will return STR1. This will serve as the base case for our recursive function.
- We will check either the first character of STR1 is larger than the first character of STR2 or STR1 is lexicographically larger than STR2, then we will insert the character STR1[0] as the next character in the merged string, and after that, invoke the recursive call to create the remaining merged string. We will return STR1[0] + largestMergedString(STR1[1:], STR2). Note, STR1[1:] denotes the substring of STR1 from index 1.
- Otherwise, If STR2 is lexicographically larger than STR1, then we will insert the character STR2[0] as the next character in the merged string and invoke the recursive call accordingly. We will return STR2[0] + largestMergedString(STR1, STR2[1:]). Note, STR2[1:] denotes the substring of STR2 from index 1.
We will merge STR1 and STR2 character by character. The idea is to observe the fact that it is always optimal to choose the next character of the merged string from the lexicographically larger string between STR1 and STR2. At each step, we will find out which string out of both strings is lexicographically greater and concatenate its first character to the end of the merged string.
Therefore, we will have to iterate till the length of strings STR1 and STR2 are more than 0. Now there will be two cases:
- If either the first character of STR1 is larger than the first character of STR2 or STR1 is lexicographically larger than STR2, then we will insert STR1[0] to the end of the merged string. As the character STR1[0] has been included in the merged string, we will update STR1 by deleting the first character.
- If STR2 is lexicographically larger than STR1, then we will insert STR2[0] to the end of the merged string. As the STR2[0] has been included in the merged string, we will update STR2 by deleting the first character.
In the end, we will return the lexicographically largest merged string of STR1 and STR2.
Algorithm:
- We will initialize the variable largestString, and it will store the lexicographically largest merged string of STR1 and STR2.
- Iterate till the length of strings STR1 and STR2 are greater than 0,
- Check If the first character of STR1 is larger than the first character of STR2 or STR1 is lexicographically larger than STR2,
- Insert STR1[0] to the end of largestString, delete the first character of the string STR1.
- Otherwise, If STR2 is lexicographically larger than STR1,
- Insert STR2[0] to the end of largestString, delete the first character of the string STR2.
- Check If the first character of STR1 is larger than the first character of STR2 or STR1 is lexicographically larger than STR2,
- Check if the length of string STR1 is greater than 0,
- Insert the remaining STR1 to the end of largestString.
- Check if the length of string STR2 is greater than 0,
- Insert the remaining STR2 to the end of largestString.
- Return the variable largestString.