La string lexicográficamente más pequeña obtenida después de concatenar una array

Dadas n strings, concatenarlas en un orden que produzca la string lexicográficamente más pequeña posible.
Ejemplos: 
 

Input :  a[] = ["c", "cb", "cba"]
Output : cbacbc
Possible strings are ccbcba, ccbacb, 
cbccba, cbcbac, cbacbc and cbaccb. 
Among all these strings, cbacbc is 
the lexicographically smallest.

Input :  a[] = ["aa", "ab", "aaa"]
Output : aaaaaab

Uno podría pensar que ordenar las strings dadas en el orden lexicográfico y luego concatenarlas produce la salida correcta. Este enfoque produce la salida correcta para entradas como [“a”, “ab”, “abc”]. Sin embargo, aplicar este método en [“c”, “cb”, “cba”] produce una entrada incorrecta y, por lo tanto, este enfoque es incorrecto.
El enfoque correcto es utilizar un algoritmo de clasificación regular. Cuando se comparan dos strings a y b para decidir si deben intercambiarse o no, no verifique si a es lexicográficamente más pequeña que b o no. En su lugar, verifique si agregar b al final de a produce una string lexicográficamente más pequeña o si agrega a al final de b. Este enfoque funciona porque queremos que la string concatenada sea lexicográficamente pequeña, no que las strings individuales estén en el orden lexicográfico. 
 

// CPP code to find the lexicographically
// smallest string
#include <bits/stdc++.h>
using namespace std;
 
// Compares two strings by checking if
// which of the two concatenations causes
// lexicographically smaller string.
bool compare(string a, string b)
{
    return (a+b < b+a);
}
 
string lexSmallest(string a[], int n)
{
    // Sort strings using above compare()
    sort(a, a+n, compare);
 
    // Concatenating sorted strings
    string answer = "";
    for (int i = 0; i < n; i++)
        answer += a[i];
 
    return answer;
}
 
// Driver code
int main()
{
    string a[] = { "c", "cb", "cba" };
    int n = sizeof(a)/sizeof(a[0]);
    cout << lexSmallest(a, n);
    return 0;
}

// Java code to find the lexicographically
// smallest string
 
class GFG {
     
// function to sort the
// array of string
static void sort(String a[], int n)
{
     
    //sort the array
    for(int i = 0;i < n;i++)
    {
        for(int j = i + 1;j < n;j++)
        {
             
            // comparing which of the
            // two concatenation causes
            // lexicographically smaller
            // string
            if((a[i] + a[j]).compareTo(a[j] + a[i]) > 0)
            {
                String s = a[i];
                a[i] = a[j];
                a[j] = s;
            }
        }
    }
}
     
static String lexsmallest(String a[], int n)
{
     
    // Sort strings
    sort(a,n);
 
    // Concatenating sorted strings
    String answer = "";
    for (int i = 0; i < n; i++)
        answer += a[i];
 
    return answer;
}
 
// Driver code
public static void main(String args[])
{
    String a[] = {"c", "cb", "cba"};
    int n = 3;
    System.out.println("lexicographically smallest string = "
                                      + lexsmallest(a, n));
 
}
}
 
// This code is contributed by Arnab Kundu

# Python 3 code to find the lexicographically
# smallest string
def lexSmallest(a, n):
  # Sort strings using above compare()
  for i in range(0,n):
    for j in range(i+1,n):
      if(a[i]+a[j]>a[j]+a[i]):
        s=a[i]
        a[i]=a[j]
        a[j]=s
 
  # Concatenating sorted strings
  answer = ""
  for i in range( n):
    answer += a[i]
  return answer
 
# Driver code
if __name__ == "__main__":
     
    a = [ "c", "cb", "cba" ]
    n = len(a)
    print(lexSmallest(a, n))
 
# This code is contributed by vibhu karnwal
 
 
   

// C# code to find
// the lexicographically
// smallest string
using System;
 
class GFG {
     
// function to sort the
// array of string
static void sort(String []a, int n)
{
     
    //sort the array
    for(int i = 0;i < n;i++)
    {
        for(int j = i + 1;j < n;j++)
        {
             
            // comparing which of the
            // two concatenation causes
            // lexicographically smaller
            // string
            if((a[i] + a[j]).CompareTo(a[j] +
                                  a[i]) > 0)
            {
                String s = a[i];
                a[i] = a[j];
                a[j] = s;
            }
        }
    }
}
     
static String lexsmallest(String []a, int n)
{
     
    // Sort strings
    sort(a,n);
 
    // Concatenating sorted
    // strings
    String answer = "";
    for (int i = 0; i < n; i++)
        answer += a[i];
 
    return answer;
}
 
// Driver code
public static void Main()
{
    String []a = {"c", "cb", "cba"};
    int n = 3;
    Console.Write("lexicographically smallest string = "
                                 + lexsmallest(a, n));
 
}
}
 
// This code is contributed by nitin mittal

<script>
// Javascript code to find the lexicographically
// smallest string
 
// function to sort the
// array of string
function sort(a,n)
{
 
    // sort the array
    for(let i = 0;i < n;i++)
    {
        for(let j = i + 1;j < n;j++)
        {
               
            // comparing which of the
            // two concatenation causes
            // lexicographically smaller
            // string
            if((a[i] + a[j])>(a[j] + a[i]) )
            {
                let s = a[i];
                a[i] = a[j];
                a[j] = s;
            }
        }
    }
}
 
 
function lexsmallest(a,n)
{
    // Sort strings
    sort(a,n);
   
    // Concatenating sorted strings
    let answer = "";
    for (let i = 0; i < n; i++)
        answer += a[i];
   
    return answer;
}
 
// Driver code
let a=["c", "cb", "cba"];
let n = 3;
document.write("lexicographically smallest string = "
                                      + lexsmallest(a, n));
       
    // This code is contributed by rag2127
</script>

cbacbc

Complejidad de tiempo: el código anterior se ejecuta en O (M * N * logN) donde N es el número de strings y M es la longitud máxima de una string.

Espacio Auxiliar: O(n)

Este artículo es una contribución de Aarti_Rathi . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.