Given two strings S and T, the task is to merge these two strings by adding one character at a time from the beginning of either string to form a resultant string. The resultant string should be lexicographically the largest string that can be formed by merging the strings S and T.
Examples:
Input: S = “dbcbb”, T = “cdbbb”
Output : dcdbcbbbbbInput : S = “neveropen“, T = “forneveropen”
Output : gforneveropeneeks
Approach: The simplest idea to solve the problem is to greedily select the first characters from the string which is lexicographically bigger than others. Therefore, Greedy algorithm and Recursion can be used to solve the problem. Follow the steps below to solve the problem:
- If either of the string lengths is 0, then return S + T as the answer.
- If S is lexicographically larger than T, then return S[0] + largestMerge(S.substr(1), T).
- Otherwise, take the first character of T and call the recursive function largestMerge(S, T.substr(1)).
Below is the implementation of the above approach:
C++
// C++ program for the approach#include <bits/stdc++.h>using namespace std;// Recursive bfunction for finding// the lexicographically largest stringstring largestMerge(string s1, string s2){ // If either of the string length is 0, // return the other string if (s1.size() == 0 || s2.size() == 0) return s1 + s2; // If s1 is lexicographically // larger than s2 if (s1 > s2) { // Take first character of s1 // and call the function return s1[0] + largestMerge(s1.substr(1), s2); } // Take first character of s2 // and recursively call function for // remaining string return s2[0] + largestMerge(s1, s2.substr(1));}// Driver Codeint main(){ // Given Input string s1 = "neveropen"; string s2 = "forneveropen"; // Function Call cout << largestMerge(s1, s2) << endl; return 0;} |
Java
// Java program for the approachpublic class Main{ // Recursive bfunction for finding // the lexicographically largest string static String largestMerge(String s1, String s2) { // If either of the string length is 0, // return the other string if (s1.length() == 0 || s2.length() == 0) return s1 + s2; // If s1 is lexicographically // larger than s2 if (s1.compareTo(s2) > 0) { // Take first character of s1 // and call the function return s1.charAt(0) + largestMerge(s1.substring(1), s2); } // Take first character of s2 // and recursively call function for // remaining string return s2.charAt(0) + largestMerge(s1, s2.substring(1)); } public static void main(String[] args) { // Given Input String s1 = "neveropen"; String s2 = "forneveropen"; // Function Call System.out.print(largestMerge(s1, s2)); }}// This code is contributed by divyesh072019. |
Python3
# Python program for the above approach# Recursive function for finding # the lexicographically largest stringdef largestMerge(s1, s2): # If either of the string length is 0, # return the other string if len(s1) == 0 or len(s2) == 0: return s1+s2 # If s1 is lexicographically # larger than s2 if(s1 > s2): # Take first character of s1 # and call the function return s1[0]+largestMerge(s1[1:], s2) # Take first character of s2 # and recursively call function for # remaining string return s2[0]+largestMerge(s1, s2[1:])# Driver codeif __name__ == '__main__': # Given Input s1 = "neveropen" s2 = "forneveropen" # Function call print(largestMerge(s1, s2)) # This code is contributed by MuskanKalra1 |
C#
// C# program for the approachusing System;class GFG { // Recursive bfunction for finding // the lexicographically largest string static string largestMerge(string s1, string s2) { // If either of the string length is 0, // return the other string if (s1.Length == 0 || s2.Length == 0) return s1 + s2; // If s1 is lexicographically // larger than s2 if (string.Compare(s1, s2) == 1) { // Take first character of s1 // and call the function return s1[0] + largestMerge(s1.Substring(1), s2); } // Take first character of s2 // and recursively call function for // remaining string return s2[0] + largestMerge(s1, s2.Substring(1)); } // Driver Code public static void Main() { // Given Input string s1 = "neveropen"; string s2 = "forneveropen"; // Function Call Console.Write(largestMerge(s1, s2)); }}// This code is contributed by ukasp. |
Javascript
<script> // JavaScript program for the approach // Recursive bfunction for finding // the lexicographically largest string const largestMerge = (s1, s2) => { // If either of the string length is 0, // return the other string if (s1.length == 0 || s2.length == 0) return s1 + s2; // If s1 is lexicographically // larger than s2 if (s1 > s2) { // Take first character of s1 // and call the function return s1[0] + largestMerge(s1.substr(1), s2); } // Take first character of s2 // and recursively call function for // remaining string return s2[0] + largestMerge(s1, s2.substr(1)); } // Driver Code // Given Input s1 = "neveropen"; s2 = "forneveropen"; // Function Call document.write(largestMerge(s1, s2)); // This code is contributed by rakeshsahni</script> |
Output
gforneveropeneeks
Time Complexity: O(M×N), where M and N are the length of string s1 and s2 respectively.
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
