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 stringset<string> visited;// To keep min length stringstring ans;// Generate the required stringvoid 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 Codeint 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 digitsimport java.io.*;import java.util.*;import java.lang.*;class neveropen { // 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 stringvisited=set() # To keep min length stringans=[]# Generate the required stringdef 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 digitsusing 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 stringlet visited = new Set()// To keep min length stringlet ans=[]// Generate the required stringfunction 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 codelet N = 2,D = 2document.write(reqString(N,D))// This code is contributed by shinjanpatra</script> |
Output:
01100
Time Complexity: O(N * DN)
Auxiliary Space: O(N * DN)
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!
