Cree una string lexicográficamente más pequeña a partir de dos strings dadas

Dadas dos strings X e Y de letras minúsculas, de longitud N y M respectivamente, la tarea es construir otra string Z realizando dos tipos de operaciones:

• Elija cualquier carácter de la string X, elimínelo de X y agréguelo al final de Z.
• Elija cualquier carácter de la string Y, elimínelo de Y y agréguelo al final de Z.

Nota: Solo puede K operaciones consecutivas en una sola string. Realice las operaciones hasta que X o Y queden vacíos.

Ejemplos :

Entrada : X = “aaaa”, Y =”bbbb”, K = 2
Salida : aabaa
Explicación : La string lexicográficamente más pequeña posible para K = 2 es “aabaa”.
Seleccione «aa» de X. Luego seleccione «b» de Y y «aa» de X nuevamente.

Entrada : X = “ccaaa”, Y =”bbeedd”, K = 3
Salida : aaabbcc

Enfoque : para resolver el problema, siga la siguiente idea:

Resolvemos este problema usando el método codicioso. 

Ordene las strings X e Y y tome los caracteres de la siguiente manera: 

• Siga seleccionando caracteres consecutivos de la string cuyos caracteres son lexicográficamente más pequeños hasta que se seleccionen K caracteres consecutivos, o se seleccionen todos los caracteres de esa string o el carácter de la otra string se vuelva lexicográficamente más pequeño.
• Si se seleccionan K caracteres consecutivos, vuelva a realizar la operación anterior en la otra string. Repita estos dos procesos hasta que al menos una de las strings quede vacía.

Siga los pasos a continuación para resolver el problema:

• Ordena las strings en orden ascendente.
• Inicialice los punteros i , j , p , q a 0 .
• Ejecute el bucle mientras alguna de las strings no esté vacía.
  • Si (X[i] < Y[j] y p < k) o q == k, entonces,
    • Agregue X[i] al final de Z e incremente i y p en 1 y establezca q = 0 .
  • De lo contrario, haga lo siguiente:
    • Agregue Y[j] al final de Z e incremente j y q en 1 y también establezca p en 0 .
• Devuelve la string resultante.

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

// C++ code to implement the above approach
  
#include <bits/stdc++.h>
using namespace std;
  
#define ll long long
  
// Function to build smallest lexicographically
// string possible for given K
string buildString(string a, string b, int k)
{
    // Calculate the sizes
    ll n = a.size();
    ll m = b.size();
  
    // Sort the strings
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
  
    // Initialize the pointers
    ll i = 0, j = 0, p = 0, q = 0;
  
    string c = "";
  
    // While any of string is non-empty
    while (i < n && j < m) {
        if ((a[i] < b[j] && p < k) || q == k) {
            c += a[i];
            p++;
            i++;
            q = 0;
        }
        else {
            c += b[j];
            q++;
            j++;
            p = 0;
        }
    }
  
    // Return resultant string
    return c;
}
  
// Driver Code
int main()
{
  
    string X = "aaaa";
    string Y = "bbbb";
    int K = 2;
  
    // Function call
    cout << buildString(X, Y, K) << endl;
  
    return 0;
}

aabaa

Complejidad de tiempo : O(N*logN +M*logM)
Espacio auxiliar : O(N+M)