Largest Merge Of Two Strings

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.

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

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.

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.

For the first test case, All possible strings constructed by merging “ac” and “b” while maintaining the order of characters are “abc”, “acb” and “bac”, among them the lexicographically largest string is “bac”. Hence, the answer is “bac” in this case. For the second test case, All possible strings constructed by merging “ca” and “ab” while maintaining the order of characters are “caab”, “caba”, “acab”, “acba” and “abca”, among them the lexicographically largest string is “caba”. Hence, the answer is “caba” in this case.

Recursive Approach

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.

Time Complexity

O((N + M) * Min(N, M)), where ‘N’ is the length of the string ‘STR1’ and ‘M’ is the length of the string ‘STR2’.

In the worst case, we are doing N + M recursive calls, and in each recursive call, it takes O(Min(N, M)) time to find the lexicographically larger string between STR1 and STR2. Hence, the overall time complexity is O((N + M) * Min(N, M)).

Space Complexity

O(N + M), where N is the length of the string ‘STR1’ and M is the length of the string ‘STR2’.

In the worst case, the recursion depth will be N + M. Hence, the overall Space Complexity is O(N + M).

Largest Merge Of Two Strings

Problem statement

Sample Input 1:

Sample Output 1:

Explanation of sample input 1:

Sample Input 2:

Sample Output 2: