Dadas dos strings ordenadas S1 y S2 de longitudes N y M respectivamente, la tarea es construir lexicográficamente la string más pequeña posible fusionando las dos strings dadas y sin cambiar el orden de aparición de los caracteres.
Ejemplos:
Entrada: S1 = “eefgkors”, S2 = “eegks”
Salida: “eeeefggkkorss”
Explicación:
La string “eeeefggkkorss” es lexicográficamente la string más pequeña que se puede formar después de fusionar las dos strings dadas S1 y S2.Entrada: S1 = “aabcdtx”, S2 = “achilp”
Salida: “aaabccdhilptx”
Enfoque ingenuo: el enfoque más simple es concatenar las dos strings dadas y ordenar la string resultante para obtener lexicográficamente la string más pequeña.
Complejidad de tiempo: O(N + M)*log(N + M))
Espacio auxiliar: O(N + M)
Enfoque eficiente: el enfoque anterior se puede optimizar mediante el uso de la técnica de dos punteros al comparar los caracteres de las strings dadas y luego construir la string requerida en consecuencia.
Siga los pasos a continuación para resolver el problema:
- Inicialice dos punteros, digamos ptr1 y ptr2 , que apunten hacia el comienzo de las strings S1 y S2 respectivamente.
- Inicialice una string ans = “”, para almacenar lexicográficamente la string resultante más pequeña.
- Iterar hasta que ptr1 sea menor que N y ptr2 sea menor que M y realizar los siguientes pasos:
- Si S1[ptr1] es menor que S2[ptr2] , agregue el carácter S1[ptr1] a la string ans . Incrementar ptr1 .
- De lo contrario, agregue el carácter S2[ptr2] a la string ans . Incrementar ptr2 .
- Después de completar los pasos anteriores, uno de los punteros no llega al final de la string.
- Por lo tanto, agregue todos los caracteres restantes de la string al final de la string ans .
- Imprima ans como la string resultante.
A continuación se muestra la implementación del enfoque anterior:
C++14
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to find lexicographically
// smallest string possible by merging
// two sorted strings
void mergeStrings(string s1, string s2)
{
// Stores length of string s1
int len1 = s1.size();
// Stores length of string s2
int len2 = s2.size();
// Pointer to beginning
// of string1 i.e., s1
int pntr1 = 0;
// Pointer to beginning
// of string2 i.e., s2
int pntr2 = 0;
// Stores the final string
string ans = "";
// Traverse the strings
while (pntr1 < len1 && pntr2 < len2) {
// Append the smaller of the
// two current characters
if (s1[pntr1] < s2[pntr2]) {
ans += s1[pntr1];
pntr1++;
}
else {
ans += s2[pntr2];
pntr2++;
}
}
// Append the remaining characters
// of any of the two strings
if (pntr1 < len1) {
ans += s1.substr(pntr1, len1);
}
if (pntr2 < len2) {
ans += s2.substr(pntr2, len2);
}
// Print the final string
cout << ans;
}
// Driver Code
int main()
{
string S1 = "abdcdtx";
string S2 = "achilp";
// Function Call
mergeStrings(S1, S2);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
class GFG{
// Function to find lexicographically
// smallest string possible by merging
// two sorted strings
static void mergeStrings(String s1, String s2)
{
// Stores length of string s1
int len1 = s1.length();
// Stores length of string s2
int len2 = s2.length();
// Pointer to beginning
// of string1 i.e., s1
int pntr1 = 0;
// Pointer to beginning
// of string2 i.e., s2
int pntr2 = 0;
// Stores the final string
String ans = "";
// Traverse the strings
while (pntr1 < len1 && pntr2 < len2)
{
// Append the smaller of the
// two current characters
if (s1.charAt(pntr1) < s2.charAt(pntr2))
{
ans += s1.charAt(pntr1);
pntr1++;
}
else
{
ans += s2.charAt(pntr2);
pntr2++;
}
}
// Append the remaining characters
// of any of the two strings
if (pntr1 < len1)
{
ans += s1.substring(pntr1, len1);
}
if (pntr2 < len2)
{
ans += s2.substring(pntr2, len2);
}
// Print the final string
System.out.println(ans);
}
// Driver Code
public static void main (String[] args)
{
String S1 = "abdcdtx";
String S2 = "achilp";
// Function Call
mergeStrings(S1, S2);
}
}
// This code is contributed by sanjoy_62
Python3
# Python3 program for the above approach # Function to find lexicographically # smallest possible by merging # two sorted strings def mergeStrings(s1, s2): # Stores length of s1 len1 = len(s1) # Stores length of s2 len2 = len(s2) # Pointer to beginning # of string1 i.e., s1 pntr1 = 0 # Pointer to beginning # of string2 i.e., s2 pntr2 = 0 # Stores the final string ans = "" # Traverse the strings while (pntr1 < len1 and pntr2 < len2): # Append the smaller of the # two current characters if (s1[pntr1] < s2[pntr2]): ans += s1[pntr1] pntr1 += 1 else: ans += s2[pntr2] pntr2 += 1 # Append the remaining characters # of any of the two strings if (pntr1 < len1): ans += s1[pntr1:pntr1 + len1] if (pntr2 < len2): ans += s2[pntr2:pntr2 + len2] # Print the final string print (ans) # Driver Code if __name__ == '__main__': S1 = "abdcdtx" S2 = "achilp" # Function Call mergeStrings(S1, S2) # This code is contributed by mohit kumar 29.
C#
// C# program for the above approach
using System;
class GFG
{
// Function to find lexicographically
// smallest string possible by merging
// two sorted strings
static void mergeStrings(string s1, string s2)
{
// Stores length of string s1
int len1 = s1.Length;
// Stores length of string s2
int len2 = s2.Length;
// Pointer to beginning
// of string1 i.e., s1
int pntr1 = 0;
// Pointer to beginning
// of string2 i.e., s2
int pntr2 = 0;
// Stores the final string
string ans = "";
// Traverse the strings
while (pntr1 < len1 && pntr2 < len2) {
// Append the smaller of the
// two current characters
if (s1[pntr1] < s2[pntr2]) {
ans += s1[pntr1];
pntr1++;
}
else {
ans += s2[pntr2];
pntr2++;
}
}
// Append the remaining characters
// of any of the two strings
if (pntr1 < len1) {
ans += s1.Substring(pntr1, len1 - pntr1);
}
if (pntr2 < len2) {
ans += s2.Substring(pntr2, len2 - pntr2);
}
// Print the final string
Console.WriteLine(ans);
}
// Driver Code
public static void Main()
{
string S1 = "abdcdtx";
string S2 = "achilp";
// Function Call
mergeStrings(S1, S2);
}
}
// This code is contributed by ukasp.
Javascript
<script>
// Javascript program for the above approach
// Function to find lexicographically
// smallest string possible by merging
// two sorted strings
function mergeStrings( s1, s2)
{
// Stores length of string s1
var len1 = s1.length;
// Stores length of string s2
var len2 = s2.length;
// Pointer to beginning
// of string1 i.e., s1
var pntr1 = 0;
// Pointer to beginning
// of string2 i.e., s2
var pntr2 = 0;
// Stores the final string
var ans = "";
// Traverse the strings
while (pntr1 < len1 && pntr2 < len2) {
// Append the smaller of the
// two current characters
if (s1[pntr1] < s2[pntr2]) {
ans += s1[pntr1];
pntr1++;
}
else {
ans += s2[pntr2];
pntr2++;
}
}
// Append the remaining characters
// of any of the two strings
if (pntr1 < len1) {
ans += s1.substr(pntr1, len1);
}
if (pntr2 < len2) {
ans += s2.substr(pntr2, len2);
}
// Print the final string
document.write( ans);
}
// Driver Code
var S1 = "abdcdtx";
var S2 = "achilp";
// Function Call
mergeStrings(S1, S2);
</script>
Producción:
aabcdcdhilptx
Complejidad temporal: O(N + M)
Espacio auxiliar: O(N + M)