Smallest number containing all possible N length permutations using digits 0 to D

0 0 5 minutes read

Given two integer N and D, the task is to find the size of the smallest string that contains all permutations of length N that can be formed using first D digits (0, 1, …, D-1).
Examples:

Input: N = 2, D = 2
Output: 01100
Explanation:
Possible permutations of length 2 from digits (0, 1) are {00, 01, 10, 11}.
“01100” is one such string that contains all the permutations as a substring.
Other possible answers are “00110”, “10011”, “11001”
Input: N = 2, D = 4
Output: 03322312113020100
Explanation:
Here all possible permutations of length 2 from digits {0, 1, 2, 3} are
00 10 20 30
01 11 21 31
02 12 22 32
03 13 23 33
“03322312113020100” is a string of minimum length that contains all the above permutations.

Approach:
Append ‘0’ N-1 times and call DFS on the string in the current state. Append all the D characters one by one. Every time after appending, check if the new string is visited or not. If so, mark it visited by inserting it into a HashSet and add this character in the answer. Recursively call the DFS function on the last D characters. Repeat this process until all possible substrings of N length from the D digits are appended to the string. Print the final string generated.
Below is the implementation of the above approach:

C++

// C++ Program to find the
// minimum length string
// consisting of all
// permutations of length N
// of D digits
#include <bits/stdc++.h>
using namespace std;
 
// Initialize set to see
// if all the possible
// permutations are present
// in the min length string
set<string> visited;
 
// To keep min length string
string ans;
 
// Generate the required string
void dfs(string curr, int D)
{
    // Iterate over all the possible
    // character
    for (int x = 0; x < D; ++x) {
        char chr = x + '0';
 
        // Append to make a new string
        string neighbour = curr + chr;
        // If the new string is not
        // visited
 
        if (visited.find(neighbour) == visited.end()) {
 
            // Add in set
            visited.insert(neighbour);
            // Call the dfs function on
            // the last d characters
            dfs(neighbour.substr(1), D);
 
            ans.push_back(chr);
        }
    }
}
string reqString(int N, int D)
{
    // Base case
    if (N == 1 && D == 1)
        return "0";
 
    visited.clear();
    ans.clear();
    string start;
 
    // Append '0' n-1 times
    for (int i = 0; i < N - 1; i++)
        start.append("0");
 
    // Call the DFS Function
    dfs(start, D);
 
    ans.append(start);
    return ans;
}
 
// Driver Code
int main()
{
    int N = 2;
    int D = 2;
    cout << reqString(N, D) << '\n';
    return 0;
}

Java

// Java Program to find the
// minimum length string
// consisting of all
// permutations of length N
// of D digits
import java.io.*;
import java.util.*;
import java.lang.*;
 
class zambiatek {
 
    // Initialize hashset to see
    // if all the possible
    // permutations are present
    // in the min length string
    static Set<String> visited;
    // To keep min length string
    static StringBuilder ans;
 
    public static String reqString(int N,
                                   int D)
    {
        // Base case
        if (N == 1 && D == 1)
            return "0";
        visited = new HashSet<>();
        ans = new StringBuilder();
 
        StringBuilder sb = new StringBuilder();
        // Append '0' n-1 times
        for (int i = 0; i < N - 1; ++i) {
            sb.append("0");
        }
        String start = sb.toString();
        // Call the DFS Function
        dfs(start, D);
        ans.append(start);
 
        return new String(ans);
    }
    // Generate the required string
    public static void dfs(String curr, int D)
    {
        // Iterate over all the possible
        // character
        for (int x = 0; x < D; ++x) {
            // Append to make a new string
            String neighbour = curr + x;
            // If the new string is not
            // visited
            if (!visited.contains(neighbour)) {
                // Add in hashset
                visited.add(neighbour);
                // Call the dfs function on
                // the last d characters
                dfs(neighbour.substring(1), D);
 
                ans.append(x);
            }
        }
    }
    // Driver Code
    public static void main(String args[])
    {
 
        int N = 2;
        int D = 2;
        System.out.println(reqString(N, D));
    }
}

Python3

# Python3 Program to find the
# minimum length string
# consisting of all
# permutations of length N
# of D digits
 
#  Initialize set to see
#  if all the possible
#  permutations are present
#  in the min length string
visited=set()
  
# To keep min length string
ans=[]
 
# Generate the required string
def dfs(curr, D):
   
    # Iterate over all possible character
    for c in range(D):
        c = str(c)
 
        # Append to make a new string
        neighbour = curr + c
 
        # If the new string is not visited
        if neighbour not in visited:
 
            # Add in set
            visited.add(neighbour)
             
            # Call the dfs function on the last d characters
            dfs(neighbour[1:], D)
 
            ans.append(c)
     
def reqString(N, D):
    # Base case
    if (N == 1 and D == 1):
        return "0"
         
    # Append '0' n-1 times
    start=''.join(['0']*(N - 1))
 
    # Call the DFS Function
    dfs(start, D)
 
    ans.extend(['0']*(N - 1))
    return ''.join(ans)
 
if __name__ == '__main__':
    N, D = 2, 2
    print(reqString(N,D))
     
    # This code is contributed by amartyaghoshgfg.

C#

// C# Program to find the minimum length string consisting
// of all permutations of length N of D digits
using System;
using System.Collections.Generic;
using System.Text;
 
public class GFG {
 
  // Initialize hashset to see if all the possible
  // permutations are present in the min length string
  static HashSet<string> visited;
   
  // To keep min length string
  static StringBuilder ans;
 
  static string reqString(int N, int D)
  {
    // Base case
    if (N == 1 && D == 1)
      return "0";
    visited = new HashSet<string>();
    ans = new StringBuilder();
 
    StringBuilder sb = new StringBuilder();
    // Append '0' n-1 times
    for (int i = 0; i < N - 1; ++i) {
      sb.Append("0");
    }
    string start = sb.ToString();
    // Call the DFS Function
    dfs(start, D);
    ans.Append(start);
 
    return ans.ToString();
  }
 
  // Generate the required string
  static void dfs(string curr, int D)
  {
    // Iterate over all the possible character
    for (int x = 0; x < D; ++x) 
    {
       
      // Append to make a new string
      string neighbour = curr + x;
       
      // If the new string is not visited
      if (!visited.Contains(neighbour)) 
      {
         
        // Add in hashset
        visited.Add(neighbour);
         
        // Call the dfs function on
        // the last d characters
        dfs(neighbour.Substring(1), D);
 
        ans.Append(x.ToString());
      }
    }
  }
 
  static public void Main()
  {
 
    // Code
    int N = 2;
    int D = 2;
    Console.WriteLine(reqString(N, D));
  }
}
 
// This code is contributed by lokeshmvs21.

Javascript

<script>
 
// JavaScript Program to find the
// minimum length string
// consisting of all
// permutations of length N
// of D digits
 
// Initialize set to see
// if all the possible
// permutations are present
// in the min length string
let visited = new Set()
 
// To keep min length string
let ans=[]
 
// Generate the required string
function dfs(curr, D){
 
    // Iterate over all possible character
    for(let c = 0;c<D;c++){
        c = parseInt(c)
 
        // Append to make a new string
        let neighbour = curr + c
 
        // If the new string is not visited
        if(visited.has(neighbour) == false){
 
            // Add in set
            visited.add(neighbour)
             
            // Call the dfs function on the last d characters
            dfs(neighbour.substring(1), D)
 
            ans.push(c)
        }
    }
 
}
     
function reqString(N, D){
    // Base case
    if (N == 1 && D == 1)
        return "0"
         
    // Append '0' n-1 times
    let start=new Array(N - 1).fill('0').join('')
 
    // Call the DFS Function
    dfs(start, D)
 
    ans.push(new Array(N - 1).fill('0'))
    return ans.join('')
}
 
// driver code
 
let N = 2,D = 2
document.write(reqString(N,D))
 
// This code is contributed by shinjanpatra
 
</script>

Output:

Time Complexity: O(N * D^N)
Auxiliary Space: O(N * D^N)

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 zambiatek!