Given two integers N and K. The task is to find the string S of minimum length such that it contains all possible strings of size N as a substring. The characters of the string can be from 0 to K-1.  
Example 1:
Input:
N = 2, K = 2
Output: 
00110
Explanation: 
There are 4 string possible of size N=2 
which contains characters 0,..K-1
(i.e "00", "01","10","11")
"00110" contains all possible string as a 
substring. It also has the minimum length
Example 2:
Input:
N = 2, K = 3
Output: 
0010211220
Explanation: There are total 9 strings possible
of size N, given output string has the minimum
length that contains all those strings as substring.
Your Task: 
You don't need to read input or print anything. Complete the function findString( ) which takes the integer N and the integer K as input parameters and returns the string.
Note: In case of multiple answers, return any string of minimum length which satisfies above condition. The driver will print the length of the string. In case of wrong answer it will print -1.
Expected Time Complexity: O(K^{N}logK)
Expected Space Complexity: O(K^{N})
Constraints:
1 ≤ N ≤ 4
1 < K < 10
1 < K^{N} < 4096

Source: geeksforgeeks | Difficulty: MEDIUM_HARD
Tags: String algorithms

Graph algorithms

Data structures

Complete search

Starter code: #User function Template for python3



class Solution:

    def findString(self, N, K):

        # code here 

Solutions:
class Solution:

	def findString(self, N, K):

		def __init__(self):
			self.a = None

		def dfs(n, k, string, ans):
			if n == 0:
				ans.add(string)
				return ans
			for i in range(k):
				ans = dfs(n - 1, k, string + str(i), ans)
			return ans

		def find(ele, string):
			vis.add(ele)
			if len(vis) == K ** N:
				self.a = string
				return True
			for y in graph[ele]:
				if y not in vis and find(y, string + y[-1]):
					return True
			vis.remove(ele)
			return False
		ans = set()
		ans = dfs(N, K, '', ans)
		graph = {}
		for i in ans:
			for z in range(K):
				ele = i[1:] + str(z)
				if ele in ans and ele != i:
					if i in graph:
						graph[i].append(ele)
					else:
						graph[i] = [ele]
		vis = set()
		for i in ans:
			if find(i, i):
				return self.a
		return self.a


class Solution:

	def findString(self, N, K):
		total = K ** N
		visited = set()
		ans = ''

		def dfs(subs, counter, res):
			if counter == total:
				nonlocal ans
				ans = res
				return True
			for digit in range(K):
				newSubstring = subs[1:] + str(digit)
				if newSubstring in visited:
					continue
				visited.add(newSubstring)
				if dfs(newSubstring, counter + 1, res + str(digit)):
					return True
				visited.remove(newSubstring)
			return
		start = ''.join(['0'] * N)
		visited.add(start)
		dfs(start, 1, start)
		return ans


class Solution:
	res = ''

	def dfs(self, ans, d, tot, N, K):
		global res
		if len(d) == tot:
			res = ans
			return True
		tmp = ''
		if N > 1:
			tmp = ans[len(ans) - N + 1:]
		for i in range(K):
			tmp += chr(48 + i)
			if tmp not in d:
				ans += chr(48 + i)
				d[tmp] = 1
				if self.dfs(ans, d, tot, N, K):
					return True
				d.pop(tmp)
				ans = ans[0:len(ans) - 1]
			tmp = tmp[0:len(tmp) - 1]
		return False

	def findString(self, N, K):
		if N == 1:
			r = ''
			for i in range(K):
				r += chr(i + 48)
			return r
		tot = pow(K, N)
		ans = '0' * N
		d = dict()
		d[ans] = 1
		self.dfs(ans, d, tot, N, K)
		return res


class Solution:

	def findString(self, N, K):
		str_char = []
		for i in range(K):
			str_char.append(str(i))
		all_str = []

		def dfs(cur_str):
			if len(cur_str) == N:
				all_str.append(cur_str)
				return
			for i in range(len(str_char)):
				dfs(cur_str + str_char[i])
		dfs('')
		graph = {}
		for a_str in all_str:
			for ch in str_char:
				next_node = a_str[1:] + ch
				if next_node in all_str and next_node != a_str:
					if a_str in graph:
						graph[a_str].append(next_node)
					else:
						graph[a_str] = [next_node]
		ans_string = ''
		visited = set()

		def find(node, cur_str):
			nonlocal ans_string
			visited.add(node)
			if len(visited) == K ** N:
				ans_string = cur_str
				return True
			for next_node in graph[node]:
				if next_node not in visited and find(next_node, cur_str + next_node[-1]):
					return True
			visited.remove(node)
			return False
		for a_str in all_str:
			if find(a_str, a_str):
				return ans_string
		return ans_string


class Solution:

	def findString(self, n, k):
		out = [0]
		combs = set()

		def dfs(n, string):
			if n == 0:
				combs.add(string)
				return
			for i in range(K):
				dfs(n - 1, string + str(i))
		vis = set()

		def find(comb, string, graph):
			vis.add(comb)
			if len(vis) == K ** N:
				out[0] = string
				return True
			for y in graph[comb]:
				if y not in vis and find(y, string + y[-1], graph):
					return True
			vis.remove(comb)
			return False
		dfs(N, '')
		graph = {}
		for i in combs:
			for z in range(K):
				comb = i[1:] + str(z)
				if comb in combs and comb != i:
					if i in graph:
						graph[i].append(comb)
					else:
						graph[i] = [comb]
		for i in combs:
			if find(i, i, graph):
				return out[0]
		return out[0]


class Solution:

	def findString(self, n, k):
		from itertools import product
		from collections import defaultdict
		dicts = defaultdict(list)
		s = ''
		if n == 1:
			return ''.join(map(str, range(k)))
		flag = True
		for i in product(range(k), repeat=n):
			i = ''.join(map(str, i))
			if flag:
				s += i
				flag = False
			else:
				dicts[i[:-1]].append(i[-1])
		while len(s) != k ** n + (n - 1):
			s += dicts[s[-(n - 1):]].pop()
		return s


class Solution:
	res = ''

	def dfs(self, ans, d, tot, N, K):
		global res
		if len(d) == tot:
			res = ans
			return True
		tmp = ''
		if N > 1:
			tmp = ans[len(ans) - N + 1:]
		for i in range(K):
			tmp += chr(48 + i)
			if tmp not in d:
				ans += chr(48 + i)
				d[tmp] = 1
				if self.dfs(ans, d, tot, N, K):
					return True
				d.pop(tmp)
				ans = ans[0:len(ans) - 1]
			tmp = tmp[0:len(tmp) - 1]
		return False

	def findString(self, N, K):
		if N == 1:
			r = ''
			for i in range(K):
				r += chr(i + 48)
			return r
		tot = pow(K, N)
		ans = '0' * N
		d = dict()
		d[ans] = 1
		self.dfs(ans, d, tot, N, K)
		return res
import sys
sys.setrecursionlimit(10 ** 6)
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(N, K) = map(int, input().split())
		ob = Solution()
		ans = ob.findString(N, K)
		ok = 1
		for i in ans:
			if ord(i) < 48 or ord(i) > K - 1 + 48:
				ok = 0
		if not ok:
			print(-1)
			continue
		d = dict()
		i = 0
		while i + N - 1 < len(ans):
			d[ans[i:i + N]] = 1
			i += 1
		tot = pow(K, N)
		if len(d) == tot:
			print(len(ans))
		else:
			print(-1)


from collections import defaultdict

class Solution:

	def findString(self, N, K):
		start = '0' * N
		self.res = ''
		visited = {start}

		def visit(node):
			for i in range(K):
				next = node[1:] + str(i)
				if next not in visited:
					visited.add(next)
					visit(next)
					self.res += str(i)
		visit(start)
		self.res += start
		return self.res
import sys
sys.setrecursionlimit(10 ** 6)
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(N, K) = map(int, input().split())
		ob = Solution()
		ans = ob.findString(N, K)
		ok = 1
		for i in ans:
			if ord(i) < 48 or ord(i) > K - 1 + 48:
				ok = 0
		if not ok:
			print(-1)
			continue
		d = dict()
		i = 0
		while i + N - 1 < len(ans):
			d[ans[i:i + N]] = 1
			i += 1
		tot = pow(K, N)
		if len(d) == tot:
			print(len(ans))
		else:
			print(-1)


import math

class Solution:

	def findString(self, n, k):
		seen = set()
		edges = []

		def dfs(node, k, A):
			for i in range(k):
				str = node + A[i]
				if str not in seen:
					seen.add(str)
					dfs(str[1:], k, A)
					edges.append(i)

		def deBruijn(n, k, A):
			startingNode = A[0] * (n - 1)
			dfs(startingNode, k, A)
			S = ''
			l = int(math.pow(k, n))
			for i in range(l):
				S += A[edges[i]]
			S += startingNode
			return S
		A = ''
		for i in range(K):
			A += chr(i + 48)
		s = deBruijn(n, k, A)
		return s
import sys
sys.setrecursionlimit(10 ** 6)
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(N, K) = map(int, input().split())
		ob = Solution()
		ans = ob.findString(N, K)
		ok = 1
		for i in ans:
			if ord(i) < 48 or ord(i) > K - 1 + 48:
				ok = 0
		if not ok:
			print(-1)
			continue
		d = dict()
		i = 0
		while i + N - 1 < len(ans):
			d[ans[i:i + N]] = 1
			i += 1
		tot = pow(K, N)
		if len(d) == tot:
			print(len(ans))
		else:
			print(-1)


class Solution:
	seen = []
	edge = []

	def dfs(node, k, A):
		for i in range(k):
			str_ = node + A[i]
			if str_ not in Solution.seen:
				Solution.seen.append(str_)
				Solution.dfs(str_[1:], k, A)
				Solution.edge.append(i)

	def findString(self, N, K):
		Solution.seen.clear()
		Solution.edge.clear()
		A = [str(i) for i in range(K)]
		sno = A[0] * (N - 1)
		Solution.dfs(sno, K, A)
		ans = ''
		l = K ** N
		for i in range(l):
			ans += A[Solution.edge[i]]
		ans += sno
		return ans
import sys
sys.setrecursionlimit(10 ** 6)
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(N, K) = map(int, input().split())
		ob = Solution()
		ans = ob.findString(N, K)
		ok = 1
		for i in ans:
			if ord(i) < 48 or ord(i) > K - 1 + 48:
				ok = 0
		if not ok:
			print(-1)
			continue
		d = dict()
		i = 0
		while i + N - 1 < len(ans):
			d[ans[i:i + N]] = 1
			i += 1
		tot = pow(K, N)
		if len(d) == tot:
			print(len(ans))
		else:
			print(-1)


class Solution:

	def __init__(self):
		self.ans = ''

	def findString(self, N, K):
		h = {}

		def dfs(a):
			for i in range(K):
				new = a + str(i)
				if new not in h:
					h[new] = True
					dfs(new[1:])
					self.ans += str(i)
		start = ''.join(['0' for _ in range(N - 1)])
		h[start] = True
		dfs(start)
		self.ans += start
		return self.ans


from itertools import product

class Solution:

	def findString(self, n, k):
		perms = set(map(lambda x: ''.join(x), product(map(str, range(k)), repeat=n)))
		ans = []

		def dfs(node):
			if not perms:
				return
			for d in map(str, range(k)):
				next_ = (node + d)[1:]
				if next_ in perms:
					perms.remove(next_)
					dfs(next_)
					ans.append(d)
		start = '0' * n
		perms.remove(start)
		dfs(start)
		return ''.join(ans) + start


class Solution:

	def __init__(self):
		self.ans = []

	def findString(self, n, k):
		if n == 1:
			l = [str(i) for i in range(k)]
			return ''.join(l)
		if k == 1:
			return '0' * n
		dic = {}

		def backtrack(s, ans):
			if len(ans) == k ** n + n - 1:
				self.ans[:] = ans[:]
				return
			if s in dic and dic[s] == k:
				return
			if s not in dic:
				dic[s] = set()
			for i in range(k):
				if i not in dic[s]:
					dic[s].add(i)
					backtrack(s[1:] + str(i), ans + [str(i)])
					if self.ans:
						return
					dic[s].remove(i)

		def gen(s):
			if len(s) == n - 1:
				backtrack(s, list(s))
				if self.ans:
					return True
				return False
			for i in range(k):
				if gen(s + str(i)):
					return True
			return False
		gen('')
		return ''.join(self.ans)


class Solution:

	def findString(self, N, K):
		ans = '0' * (N - 1)
		str_set = set()
		for i in range(K ** N):
			substr = ans[-N + 1:] if N > 1 else ''
			for j in range(K - 1, -1, -1):
				if substr + str(j) not in str_set:
					str_set.add(substr + str(j))
					ans += str(j)
					break
		return ans[-1::-1]