Given a string 
where 
. Assume that all the characters in are unique. The task is to compute the minimum length of a string which consists of all the permutations of the given string in any order.
Note: All permutations must be present as a substring in the resulting string.
Examples:
Input : ab Output : 3 The resulting string is aba. Input : abc Output : 9 The resulting string is abcabacba.
Approach: The answer to the above problem is simple.
- If the length of string is 1, then answer is 1.
- If the length of string is 2, then answer is 3.
- If the length of string is 3, then answer is 9.
So, after observing the output we can see that if the length of the string is n, then answer will be 1! + 2! + … + n!. Hence we can precompute the result upto n = 26 in vector of strings.
Implementation:
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 stringvoid 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 programint 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 programs = "abc"# function call to print minimum length of stringminLength(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 stringfunction 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 stringminLength($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 stringminLength(s);// This code is contributed by 29AjayKumar </script> |
Output
9
Time Complexity: 
Auxiliary Space: O(1)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!