We need to find a ‘S’ string that contains all possible permutations of length ‘N’ and allowed characters ‘0’ to ‘K’. So there can be total ‘(K + 1) ^ N’ possible permutations, For example if ‘N’ is 2 and ‘K’ is 1 then total possible permutations are { 00, 01, 10, 11} i.e 2 ^ 2 = 4 total possible. We can simply concatenate each one to find such ‘S’ i.e ‘S’  = “00011011”, but in order to minimise the length of ‘S we need to make sure that every permutation occurs exactly once in the ‘S’. Such strings are made from De Bruijn sequence. We can visualise the given Problem as a directed graph structure where each node represents distinct possible permutations of length ‘N’ and a edge from ‘node1’ to ‘node2’ represents that we can add a digit in range [0, k] to the suffix of length ‘N - 1’ of ‘node1’ to make ‘node2’.

For example for ‘N’ = 2 and ‘K’ = 2, the graph structure will look like below.

Now we just need to find a Hamiltonian Path in the above graph and add the character of edges in the path to the starting string. For example, let's start with ‘00’ and initialize our answer with ‘00’.

• We move to ‘01’ and add ‘1’ to answer.
• Now we will move to ‘11’ because if we move to ‘10’, we got stuck, so add ‘1’ to answer.
• Now from ‘11’ we move to ‘10’, thus completing our path, and hence the answer becomes ‘00110’.

We can run a dfs with a backtrack to find such a path.

Algorithm:

• Let the given integers be ‘N’ and ‘K’
• Declare a function dfs to visit all nodes in the graph once.
• Declare a hashmap of string say ‘visited’ to keep track of the visited strings (nodes) in the graph.
• Declare a string ‘answer’ and initialize it with ‘000… N times’.
• Insert ‘answer’ into ‘visited’.
• Call the dfs function to find a hamiltonian path.
• Return ‘answer’.

Description of ‘dfs’ function

This is a boolean function that returns true if we find a valid path by traversing an edge, else return false.

The function will take four-parameter:

‘N’: The given length of numbers

‘K’: allowed range of digits

‘answer’: global answer string

‘visited’:  A hashmap to keep track of visited nodes.

bool dfs ( N, K, answer, visited ):

• If we have visited all the nodes i.e. the size of ‘visited’ is (‘K’ + 1) ^ ‘N’
  • return true.
• Run a loop from ‘i’ = 0 to ‘K’
  • Declare a string say ‘currNode’ and set it to substring ‘answer(1, N-1)’.
  • Add string of ‘i’ to ‘currNode’.
  • If ‘currNode’ is not visited.
    • Insert ‘currNode’ into ‘visited’.
    • Check if adding ‘i’ to 'answer' is a valid path or not i.e If dfs( ‘answer’ + ‘str(i)’) == true then
      • Return true.
    • Else:
      • Remove ‘currNode’ from ‘visited’, as we cannot add ‘i’ to ‘answer’ now.
• Return false.

O(N * ((K + 1) ^ N) ) where ‘N’ and ‘K’ are the given integers.

As we are using a hashmap to store total possible permutations that is (‘K’ + 1) ^ ‘N’ in the count, that takes O(N * ((K + 1) ^ N) ) space. Also, we are calling recursive functions so in the worst case, the recursion stack will store (K + 1) ^ N function calls that take O((K + 1) ^ N) space. Hence the overall space complexity is O(N * ((K + 1) ^ N) )

O(N * ((K + 1) ^ N) ) where ‘N’ and ‘K’ are the given integers.

As there are (‘K’ + 1) ^ ‘N’ total possible permutations and we are iterating over each of them exactly once that takes O((K + 1) ^ N) time. Also, we are maintaining a hashmap/ unordered set of strings of size ‘N’ to keep track of visited permutation, which takes O( size of string) time for lookup and insertions. Hence the overall time complexity is O(N * ((K + 1) ^ N) ).

/*

    Time Complexity: O(N * ((K + 1) ^ N) )

    Space Complexity: O(N * ((K + 1) ^ N) )



    where ‘N’ and ‘K’ are the given integers.

*/



#include



// DFS function to find a hamiltonian path.

bool dfs(int n, int k, string &answer, unordered_set &visited)

{

    // If we had visited all the possile strings

    if(visited.size() == pow((k +1), n))

    {

        return true;

    }



    //Run through each edge from current node.

    for(int i = 0; i <= k; i++)

    {

        // Get the last 'n' - 1 digits from the answer. 

        string currNode = answer.substr(answer.size() - n + 1);



        // Add current edge in 'currNode'.

        currNode.push_back( '0' + i);



        // If the node is not visited

        if(visited.find(currNode) == visited.end())

        {

            visited.insert(currNode);



            // Add current edge into answer.

            answer.push_back('0' + i);



            // If the current edge is a valid path then return true

            if(dfs(n, k, answer, visited) == true)

            {

                return true;

            }



            // If the current edge is not a valid path then backtrack and try next edge.

            answer.pop_back();

            visited.erase(currNode);

        }

    }



    // If path is not found return false.

    return false;

}



string getMinString(int n, int k)

{

    // Initialize a empty string to store final answer.

    string answer = "";



    // Start with adding '0'- n times in answer.

    for(int i = 0; i < n; i++)

    {

        answer.push_back('0');

    }



    // Declare a unordered set to keep track of visited nodes.

    unordered_set visited;



    visited.insert(answer);



    // Call dfs function

    dfs(n, k, answer, visited);



    // Return answer.

    return answer;

}

'''

    Time Complexity: O(N * ((K + 1) ^ N) )

    Space Complexity: O(N * ((K + 1) ^ N) )



    where ‘N’ and ‘K’ are the given integers.

'''

answer = ""

visited = set()



# DFS function to find a hamiltonian path.

def dfs(n, k):



    global answer

    global visited



    # If we had visited all the possile strings

    if(len(visited) == ((k + 1)**n)):

        return True



    # Run through each edge from current node.

    for i in range(k + 1):



        lenght = len(answer)



        # Get the last 'n' - 1 digits from the answer. 

        currNode = answer[(lenght - n + 1): lenght]



        # Add current edge in 'currNode'.

        currNode += (str(i))



        # If the node is not visited

        if currNode not in visited:

            visited.add(currNode)



            # Add current edge into answer.

            answer += (str(i))



            # If the current edge is a valid path then return True

            if(dfs(n, k) == True):

                return True



            # If the current edge is not a valid path then backtrack and try next edge.

            answer = answer[0 : (len(answer) - 1)]

            visited.remove(currNode)

        

    # If path is not found return false.

    return False



def getMinString(n, k):



    global answer

    global visited



    # Initialize a empty string to store final answer.

    answer = ""



    # Start with adding '0'- n times in answer.

    for i in range(n):

        answer += "0"



    # Declare a unordered set to keep track of visited nodes.

    visited = set()



    visited.add(answer)



    # Call dfs function

    dfs(n, k)



    # Return answer.

    return answer

/*
    Time Complexity: O(N * ((K + 1) ^ N) )
    Space Complexity: O(N * ((K + 1) ^ N) )

    where 'N' and 'K' are the given integers.
*/

import java.util.HashSet;
 
public class Solution {

    // Declaring 'answer' and 'visited' as globally.
    static StringBuilder answer = new StringBuilder();
    static HashSet visited = new HashSet();

    // DFS function to find a hamiltonian path.
    static boolean dfs(int n, int k) {

        // If we had visited all the possile strings.
        if(visited.size() == (int)Math.pow( (k + 1), n)) {
            return true;
        }

        //Run through each edge from current node.
        for(int i = 0; i <= k; i++) {
            
            // Get the last 'n' - 1 digits from the answer. 
            String currNode = answer.substring(answer.length() - n + 1);
            
            // Add current edge in 'currNode'.
            currNode += ((char)(i + '0'));

            // If the node is not visited.
            if(!visited.contains(currNode)) {

                visited.add(currNode);

                // Add current edge into answer.
                answer.append((char)(i + '0'));

                // If the current edge is a valid path then return true.
                if(dfs(n, k) == true) {
                    return true;
                }

                // If the current edge is not a valid path then backtrack and try next edge.
                answer.setLength(answer.length()-1);
                visited.remove(currNode);
            }
        }

        // If path is not found return false.
        return false;
    }

    public static String getMinString(int n, int k) {

        // Initialize a empty string to store final answer.
        answer = new StringBuilder();

        // Start with adding '0'- n times in answer.
        for(int i = 0; i < n; i++) {
            answer.append('0');
        }

        // Declare a unordered set to keep track of visited nodes.
        visited = new HashSet();
         
        visited.add(answer.toString());

        // Call dfs function.
        dfs(n, k);  

        // Return answer.
        return answer.toString();
    }
}

As we see in the previous approach, the required string can be obtained from the De Bruijn sequence. The idea is to start with ‘N’ 0’s as an initial answer and greedily add digits until we get all the possible permutations. But in order to prevent stuck situations as we see in the example of the previous approach, we need to add digits in a post-order way. i.e starting from ‘K’ to ‘0’. For example ‘N’ = 2 and ‘K’ is 1, and if the previous permutation is ‘01’ then we will first add ‘1’ to get ‘11’ and then add ‘0’.

Algorithm:

• Let the given integers be ‘N’ and ‘K’
• Declare a hashmap of string say ‘visited’ to keep track of the visited strings.
• Declare a string ‘answer’ and initialize it with ‘000… N times’.
• Insert ‘answer’ into ‘visited’.
• Run a loop until the size of ‘visited’ is less than (‘K’ + 1) ^ ‘N’, i.e we visited all permutations.
  • Declare a string say ‘previous’ to store the last ‘N - 1’ characters of ‘answer’.
  • Run a loop from ‘i’ = K to ‘0’.
    • If ‘previous’ + string form of ‘i’ is not visited
      • Add ‘previous’ + str(‘i’) into ‘visited’.
      • Add str(‘i’) in ‘answer’.
      • Break the current loop.
• Return ‘answer’.

O(N * ((K + 1) ^ N) ) where ‘N’ and ‘K’ are the given integers.

As we are using a hashmap to store total possible permutations of size ‘N’ that is (‘K’ + 1) ^ ‘N’ in the count, that takes O(N * ((K + 1) ^ N) ) space.

O(N * ((K + 1) ^ N) ) where ‘N’ and ‘K’ are the given integers.

As there are (‘K’ + 1) ^ ‘N’ total possible permutations and we are iterating over each of them exactly once that takes O((K + 1) ^ N) time. Also, we are maintaining a hashmap/ unordered set of strings of size ‘N’ to keep track of visited permutation, which takes O( size of string) 

time for lookup and insertions. Hence the overall time complexity is O(N * ((K + 1) ^ N) )

/*

    Time Complexity: O(N * ((K + 1) ^ N) )

    Space Complexity: O(N * ((K + 1) ^ N) )



    where ‘N’ and ‘K’ are the given integers.

*/



#include



string getMinString(int n, int k)

{

    // Initialize a empty string to store final answer.

    string answer = "";



    // Start with adding '0'- n times in answer.

    for(int i = 0; i < n; i++)

    {

        answer.push_back('0');

    }



    // Declare a unordered set to keep track of visited nodes.

    unordered_set visited;



    visited.insert(answer);



    // Run a loop until we find all permutations.

    while (visited.size() < pow( (k +1), n))

    {

        // Get the last 'n' - 1 digits from 'answer'.

        string previous = answer.substr(answer.size()-n+1);



        // Run a loop from 'k' to '0'.

        for(int i = k; i >= 0; i--)

        {

            // Declare a string 'currStr' to store current string by adding str of 'i' into 'previous'.

            string currStr = previous;

            currStr.push_back(i + '0');



            // If current string is not visited.

            if(visited.find(currStr) == visited.end())

            {

                visited.insert(currStr);

                answer.push_back( i + '0');

                break;

            }

        }

    }



    // Return answer.

    return answer;

}

'''

    Time Complexity: O(N * ((K + 1) ^ N) )

    Space Complexity: O(N * ((K + 1) ^ N) )



    where ‘N’ and ‘K’ are the given integers.

'''



def getMinString(n, k):

    

    # Initialize a empty string to store final answer.

    answer = ""



    # Start with adding '0'- n times in answer.

    for i in range(n):

        answer += "0"



    # Declare a unordered set to keep track of visited nodes.

    visited = set()



    visited.add(answer)



    # Run a loop until we find all permutations.

    while (len(visited) < ((k +1)**n)):



        lenght = len(answer)



        # Get the last 'n' - 1 digits from 'answer'.

        previous = answer[(lenght - n + 1) : lenght]



        # Run a loop from 'k' to '0'.

        for i in range(k, -1, -1):



            # Declare a string 'currStr' to store current string by adding str of 'i' into 'previous'.

            currStr = previous

            currStr += str(i)



            # If current string is not visited.

            if currStr not in visited:

                visited.add(currStr)

                answer += str(i)

                break



    # Return answer.

    return answer

/*
    Time Complexity: O(N * ((K + 1) ^ N) )
    Space Complexity: O(N * ((K + 1) ^ N) )

    where 'N' and 'K' are the given integers.
*/

import java.util.HashSet;
 
public class Solution {
    public static String getMinString(int n, int k) {

        // Initialize a empty string to store final answer.
        StringBuilder answer = new StringBuilder();

        // Start with adding '0'- n times in answer.
        for(int i = 0; i < n; i++) {
            answer.append('0');
        }

        // Declare a unordered set to keep track of visited nodes.
        HashSet visited = new HashSet();
         
        visited.add(answer.toString());

        // Run a loop until we find all permutations.
        while (visited.size() < (int)Math.pow( (k + 1), n)) {

            // Get the last 'n' - 1 digits from 'answer'.
            String previous = answer.substring(answer.length() - n + 1);
            
            // Run a loop from 'k' to '0'.
            for(int i = k; i >= 0; i--) {

                // Declare a string 'currStr' to store current string by adding str of 'i' into 'previous'.
                StringBuilder currStr = new StringBuilder(previous);
                currStr.append((char)(i+'0'));

                // If current string is not visited. 
                if(!visited.contains(currStr.toString())) {
                   visited.add(currStr.toString());
                   answer.append((char)(i + '0'));
                   break;
                }
            }
        }

        // Return answer.
        return answer.toString();
    }
}