Longitud mínima de la string que tiene todas las permutaciones de la string dada.

Dada una string  donde,  . Suponga que todos los caracteres en  son únicos. La tarea es calcular la longitud mínima de una string que consta de todas las permutaciones de la string dada en cualquier orden.
Nota: Todas las permutaciones deben estar presentes como una substring en la string resultante.
Ejemplos: 
 

Input : ab
Output : 3
The resulting string is aba.

Input : abc
Output : 9
The resulting string is abcabacba.

Enfoque: La respuesta al problema anterior es simple. 

1. Si la longitud de la string es 1 , entonces la respuesta es 1 .
2. Si la longitud de la string es 2 , entonces la respuesta es 3 .
3. Si la longitud de la string es 3 , entonces la respuesta es 9 .

Entonces, después de observar la salida, podemos ver que si la longitud de la string es n , ¡entonces la respuesta será 1! + 2! + … + n! . Por lo tanto, podemos precalcular el resultado hasta n = 26 en el vector de strings.
A continuación se muestra la implementación del enfoque anterior. 
 

// C++ implementation to find the minimum length of
// string having all permutation of the given string
#include <bits/stdc++.h>
using namespace std;
 
// function to find minimum length of required string
void minLength(string s)
{
 
    // Precomputed answers for all String.
    vector<string> minlen = { "0", "1", "3", "9", "33", "153", "872",
                    "5912", "46232", "409112", "4037912", "43954712",
                    "522956312", "6749977112", "93928268312",
                    "1401602636312", "22324392524312", "378011820620312",
                    "6780385526348312", "128425485935180312",
                    "2561327494111820312", "53652269665821260312",
                     "1177652997443428940312", "27029669736328405580312",
                     "647478071469567844940312", "16158688114800553828940312",
                     "419450149241406189412940312" };
 
    cout << minlen[s.size()];
}
 
// Driver program
int main()
{
    string s = "abc";
 
    // function call to print minimum length of string
    minLength(s);
 
    return 0;
}
// This code is written by
// Sanjit_Prasad

// Java implementation to find
// the minimum length of string
// having all permutation of
// the given string
class GFG
{
 
// function to find minimum
// length of required string
static void minLength(String s)
{
 
    // Precomputed answers for all String.
    String minlen[] = { "0", "1", "3", "9", "33", "153", "872",
                        "5912", "46232", "409112", "4037912",
                        "43954712", "522956312", "6749977112",
                        "93928268312", "1401602636312",
                        "22324392524312", "378011820620312",
                        "6780385526348312", "128425485935180312",
                        "2561327494111820312", "53652269665821260312",
                        "1177652997443428940312", "27029669736328405580312",
                        "647478071469567844940312",
                        "16158688114800553828940312",
                        "419450149241406189412940312"};
 
    System.out.println(minlen[s.length()]);
}
 
// Driver code
public static void main (String args[])
{
    String s = "abc";
 
    // function call to print
    // minimum length of string
    minLength(s);
 
}
}
 
// This code is contributed by ANKITRAI1

# Python implementation to find the minimum length of
# string having all permutation of the given string.
 
# function to find minimum length of required string.
def minLength(s):
 
    # Precomputed answers for all String.
    minlen = ["0", "1", "3", "9", "33", "153", "872", "5912", "46232", "409112", "4037912", "43954712",
              "522956312", "6749977112", "93928268312", "1401602636312", "22324392524312",
              "378011820620312", "6780385526348312", "128425485935180312", "2561327494111820312",
              "53652269665821260312", "1177652997443428940312", "27029669736328405580312",
              "647478071469567844940312", "16158688114800553828940312", "419450149241406189412940312"]
 
    print(minlen[len(s)])
 
 
# Driver program
s = "abc"
 
# function call to print minimum length of string
minLength(s)
 
# This code is written by
# Sanjit_Prasad

// C# implementation to find
// the minimum length of string
// having all permutation of
// the given string
using System;
 
class GFG
{
 
// function to find minimum
// length of required string
static void minLength(String s)
{
 
    // Precomputed answers for all String.
    String[] minlen = { "0", "1", "3", "9", "33", "153", "872",
                        "5912", "46232", "409112", "4037912",
                        "43954712", "522956312", "6749977112",
                        "93928268312", "1401602636312",
                        "22324392524312", "378011820620312",
                        "6780385526348312", "128425485935180312",
                        "2561327494111820312", "53652269665821260312",
                        "1177652997443428940312", "27029669736328405580312",
                        "647478071469567844940312",
                        "16158688114800553828940312",
                        "419450149241406189412940312"};
 
    Console.WriteLine(minlen[s.Length]);
}
 
// Driver code
public static void Main ()
{
    String s = "abc";
 
    // function call to print
    // minimum length of string
    minLength(s);
}
}
 
// This code is contributed
// by Akanksha Rai(Abby_akku)

<?php
// PHP implementation to find the
// minimum length of string having
// all permutation of the given string
 
// function to find minimum length
// of required string
function minLength($s)
{
    // Precomputed answers for all String.
    $minlen = array("0", "1", "3", "9", "33", "153", "872",
                    "5912", "46232", "409112", "4037912",
                    "43954712", "522956312", "6749977112",
                    "93928268312", "1401602636312",
                    "22324392524312", "378011820620312",
                    "6780385526348312", "128425485935180312",
                    "2561327494111820312", "53652269665821260312",
                    "1177652997443428940312", "27029669736328405580312",
                    "647478071469567844940312", "16158688114800553828940312",
                    "419450149241406189412940312");
 
    echo $minlen[strlen($s)];
}
 
// Driver Code
$s = "abc";
 
// function call to print
// minimum length of string
minLength($s);
 
// This code is written by
// ash264
?>

<script>
// javascript implementation to find
// the minimum length of string
// having all permutation of
// the given string // function to find minimum
// length of required string
function minLength(s)
{
 
    // Precomputed answers for all String.
    minlen = [ "0", "1", "3", "9", "33", "153", "872",
                        "5912", "46232", "409112", "4037912",
                        "43954712", "522956312", "6749977112",
                        "93928268312", "1401602636312",
                        "22324392524312", "378011820620312",
                        "6780385526348312", "128425485935180312",
                        "2561327494111820312", "53652269665821260312",
                        "1177652997443428940312", "27029669736328405580312",
                        "647478071469567844940312",
                        "16158688114800553828940312",
                        "419450149241406189412940312"];
 
    document.write(minlen[s.length]);
}
 
// Driver code
s = "abc";
 
// function call to print
// minimum length of string
minLength(s);
 
// This code is contributed by 29AjayKumar
 
</script>

Producción:

9

Complejidad del tiempo: