Lexicográficamente más grande posible fusionando dos strings agregando un carácter a la vez

Dadas dos strings S y T, la tarea es fusionar estas dos strings agregando un carácter a la vez desde el comienzo de cualquiera de las strings para formar una string resultante . La string resultante debería ser lexicográficamente la string más grande que se puede formar fusionando las strings S y T . 

Ejemplos:

Entrada: S = “dbcbb”, T = “cdbbb”
Salida: dcdbcbbbbb

Entrada: S = « geeks «, T = « forgeeks»
Salida: gforgeekseeks

Enfoque: la idea más simple para resolver el problema es seleccionar con avidez los primeros caracteres de la string que es lexicográficamente más grande que otros. Por lo tanto, el algoritmo Greedy y la Recursión se pueden usar para resolver el problema. Siga los pasos a continuación para resolver el problema:

•  Si alguna de las longitudes de string es 0 , devuelve S + T como respuesta.
• Si S es lexicográficamente más grande que T, devuelve S[0] + largeMerge(S.substr(1), T) .
• De lo contrario, tome el primer carácter de T y llame a la función recursiva más grandeMerge(S, T.substr(1)).

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Recursive  bfunction for finding
// the lexicographically largest string
string 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 Code
int main()
{
    // Given Input
    string s1 = "geeks";
    string s2 = "forgeeks";
 
    // Function Call
    cout << largestMerge(s1, s2) << endl;
 
    return 0;
}

// Java program for the approach
public 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 = "geeks";
        String s2 = "forgeeks";
  
        // Function Call
        System.out.print(largestMerge(s1, s2));
    }
}
 
// This code is contributed by divyesh072019.

# Python program for the above approach
 
# Recursive function for finding
# the lexicographically largest string
def 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 code
if __name__ == '__main__':
   
    # Given Input
    s1 = "geeks"
    s2 = "forgeeks"
 
    # Function call
    print(largestMerge(s1, s2))
     
# This code is contributed by MuskanKalra1

// C# program for the approach
using 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 = "geeks";
        string s2 = "forgeeks";
 
        // Function Call
        Console.Write(largestMerge(s1, s2));
    }
}
 
// This code is contributed by ukasp.

<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 = "geeks";
    s2 = "forgeeks";
 
    // Function Call
    document.write(largestMerge(s1, s2));
     
    // This code is contributed by rakeshsahni
</script>

gforgeekseeks

Complejidad temporal: O(M×N), donde M y N son la longitud de la string s1 y s2 respectivamente.
Espacio Auxiliar: O(1)