Strings of Numbers

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 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) ).

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