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

Dada una string  S   donde,  1\leq length\; of\; S\leq 26   . Suponga que todos los caracteres en  S   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++

// 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

// 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

# 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#

// 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
// 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
?>

Javascript

<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: O(1)
 

Publicación traducida automáticamente

Artículo escrito por Sanjit_Prasad y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *