La string lexicográficamente más grande posible agregando repetidamente el primer carácter de dos strings dadas

Dadas dos strings S1 y S2 que consisten en N y M caracteres en minúsculas, la tarea es construir la string lexicográficamente más grande agregando repetidamente el primer carácter de cualquiera de las strings y eliminando ese carácter de la string elegida.

Ejemplos:

Entrada: S1 = “dbcbb”, S2 = “cdbbb”
Salida: “dcdbcbbbbb”
Explicación:
Sea ans la string lexicográficamente más grande que inicialmente está vacía y realice los siguientes pasos para generar la string resultante:
Tome el primer carácter de s1: ans = “d”, s1 = “bcbb”, s2 = “cdbbb”
Tomar el primer carácter de s2: ans = “dc”, s1 = “bcbb”, word2 = “dbbb”
Tomar el primer carácter de s2: ans = “dcd”, s1 = “bcbb”, palabra2 = “bbb”
Tomar el primer carácter de s1: ans = “dcdb”, s1 = “cbb”, palabra2 = “bbb”
Tomar el primer carácter de s1: ans = “dcbdc”, s1 = “bb ”, palabra2 = “bbb”
Agregue las 5 b restantes de s1 y s2 al final de ans. Por lo tanto, imprima «dcdbcbbbbb» como la string resultante.

Entrada: S1 = “xyzxyz”, S2 = “xywzxyx”
Salida: “xyzxyzxywzxyx”

Enfoque: el problema dado se puede resolver utilizando el enfoque de dos puntos . Siga los pasos a continuación para resolver el problema:

• Inicialice una string vacía, diga fusionar como «» para almacenar la string lexicográficamente más grande .
• Inicialice dos punteros , digamos i como 0 , j como 0 para atravesar ambas strings simultáneamente.
• Atraviese la cuerda hasta que cualquiera de las cuerdas se haya utilizado por completo.
  • Si la substring palabra1[i, N – 1] es lexicográficamente mayor que o igual a la substring palabra2[j, M – 1] , agregue el carácter palabra1[i] al final de la combinación de strings e incremente el puntero i en 1 .
  • De lo contrario, agregue el carácter word2[i] al final de la combinación de strings e incremente el puntero j en 1 .
• Después de completar los pasos anteriores, imprima la combinación de strings como la string resultante.

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

// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
 
// Function to make the lexicographically
// largest string by merging two strings
string largestMerge(string word1,
                    string word2)
{
    // Stores the resultant string
    string merge = "";
 
    while (word1.size() != 0
           || word2.size() != 0) {
 
        // If the string word1 is
        // lexicographically greater
        // than or equal to word2
        if (word1 >= word2) {
 
            // Update the string merge
            merge = merge + word1[0];
 
            // Erase the first index
            // of the string word1
            word1.erase(word1.begin() + 0);
        }
 
        // Otherwise
        else {
 
            // Update the string merge
            merge = merge + word2[0];
 
            // Erase the first index of
            // the string word2
            word2.erase(word2.begin() + 0);
        }
    }
 
    // Return the final string
    return merge;
}
 
// Driver Code
int main()
{
    string S1 = "xyzxyz";
    string S2 = "xywzxyx";
    cout << largestMerge(S1, S2);
 
    return 0;
}

// Java program for the above approach
import java.io.*;
 
class GFG {
 
// Function to make the lexicographically
// largest string by merging two strings
static String largestMerge(String word1,
                           String word2)
{
     
    // Stores the resultant string
    String merge = "";
 
    while (word1.length() != 0 ||
           word2.length() != 0)
    {
         
        // If the string word1 is
        // lexicographically greater
        // than or equal to word
        if (word1.compareTo(word2) == 0 || ( word1.compareTo(word2) > 0))
        {
 
            // Update the string merge
            merge = merge + word1.charAt(0);
 
            // Erase the first index
            // of the string word1
            word1 = word1.substring(1);
        }
 
        // Otherwise
        else
        {
             
            // Update the string merge
            merge = merge + word2.charAt(0);
 
            // Erase the first index of
            // the string word2
            word2 = word2.substring(1);
        }
    }
 
    // Return the final string
    return merge;
}
 
// Driver Code
public static void main(String[] args)
{
    String S1 = "xyzxyz";
    String S2 = "xywzxyx";
     
    System.out.println(largestMerge(S1, S2));
}
}
 
// This code is contributed by sanjoy_62.

# Python program for the above approach
 
# Function to make the lexicographically
# largest string by merging two strings
def largestMerge(word1, word2):
   
     # Stores the resultant string
    merge = ""
    while len(word1) != 0 or len(word2) != 0:
       
          # If the string word1 is
        # lexicographically greater
        # than or equal to word2
        if word1 >= word2:
           
          # Update the string merge
            merge = merge + word1[0]
             
             # Erase the first index
            # of the string word1
            word1 = word1[1:]
             
            #  Otherwise
        else:
           
          # Update the string merge
            merge = merge + word2[0]
             
             # Erase the first index
            # of the string word2
            word2 = word2[1:]
             
    # Return the final string       
    return merge
 
# Driver code
S1 = "xyzxyz"
S2 = "xywzxyx"
print(largestMerge(S1, S2))
 
# This code is contributed by Parth Manchanda

// C# program for the above approach
using System;
using System.Collections.Generic;
 
class GFG{
 
// Function to make the lexicographically
// largest string by merging two strings
static string largestMerge(string word1,
                           string word2)
{
     
    // Stores the resultant string
    string merge = "";
 
    while (word1.Length != 0 ||
           word2.Length != 0)
    {
         
        // If the string word1 is
        // lexicographically greater
        // than or equal to word2
        if (String.Compare(word1, word2) == 0 ||
            String.Compare(word1, word2) > 0)
        {
 
            // Update the string merge
            merge = merge + word1[0];
 
            // Erase the first index
            // of the string word1
            word1 = word1.Substring(1);
        }
 
        // Otherwise
        else
        {
             
            // Update the string merge
            merge = merge + word2[0];
 
            // Erase the first index of
            // the string word2
            word2 = word2.Substring(1);
        }
    }
 
    // Return the final string
    return merge;
}
 
// Driver Code
public static void Main()
{
    string S1 = "xyzxyz";
    string S2 = "xywzxyx";
     
    Console.Write(largestMerge(S1, S2));
 
}
}
 
// This code is contributed by SURENDRA_GANGWAR

<script>
// Javascript program for the above approach
 
// Function to make the lexicographically
// largest let by merging two lets
function largestMerge(word1, word2)
{
     
    // Stores the resultant let
    let merge = "";
 
    while (word1.length != 0 ||
           word2.length != 0)
    {
         
        // If the let word1 is
        // lexicographically greater
        // than or equal to word
        if (word1.localeCompare(word2) == 0 || ( word1.localeCompare(word2) > 0))
        {
 
            // Update the let merge
            merge = merge + word1[0];
 
            // Erase the first index
            // of the let word1
            word1 = word1.substring(1);
        }
 
        // Otherwise
        else
        {
             
            // Update the let merge
            merge = merge + word2[0];
 
            // Erase the first index of
            // the let word2
            word2 = word2.substring(1);
        }
    }
 
    // Return the final let
    return merge;
}
 
// Driver Code
 
      let S1 = "xyzxyz";
    let S2 = "xywzxyx";
     
    document.write(largestMerge(S1, S2));
 
// This code is contributed by splevel62.
</script>

xyzxyzxywzxyx

Complejidad temporal: O(N*M)
Espacio auxiliar: O(1)