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 should be from integers ranging from 0 to K-1. Example 1:Input:N = 2, K = 2Output: 00110Explanation: Allowed characters are from 0 to k-1 (i.e., 0 and 1).There are 4 string possible of size N=2 (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 = 3Output: 0010211220Explanation: Allowed characters are from 0 to k-1 (i.e., 0, 1 and 2).There are total 9 strings possibleof size N, given output string has the minimumlength 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(KNlogK)Expected Space Complexity: O(KNN)Constraints:1 ≤ N ≤ 41 < K < 101 < KNN < 106
Question
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 should be from integers ranging from 0 to K-1. Example 1:Input:N = 2, K = 2Output: 00110Explanation: Allowed characters are from 0 to k-1 (i.e., 0 and 1).There are 4 string possible of size N=2 (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 = 3Output: 0010211220Explanation: Allowed characters are from 0 to k-1 (i.e., 0, 1 and 2).There are total 9 strings possibleof size N, given output string has the minimumlength 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(KNlogK)Expected Space Complexity: O(KNN)Constraints:1 ≤ N ≤ 41 < K < 101 < KNN < 106
Solution
The problem is asking to generate a string of minimum length that contains all possible substrings of length N, using digits from 0 to K-1.
Here is a Python solution using De Bruijn sequence:
from collections import deque
def findString(N, K):
sequence = deque()
sequence.extend([0]*N)
sequence_length = 1
for _ in range(K**N):
sequence.append(sequence[-N+1:]*K + sequence_length)
sequence_length = sequence_length * K % (K**N)
return "".join(map(str, sequence))
print(findString(2, 2)) # Output: 00110
print(findString(2, 3)) # Output: 0010211220
This solution works by generating a De Bruijn sequence, which is a cyclic sequence of a given alphabet (in this case, the digits from 0 to K-1) where every possible substring of a certain length (in this case, N) appears exactly once. The time complexity is O(K^N), and the space complexity is O(K^N), which meet the problem's constraints.
Similar Questions
Given 2 strings A and B, find the smallest substring of B having all the characters of A, in any order.Input FormatThe first line of input contains T - the number of test cases. It's followed by T lines, each line containing 2 space-separated strings - A and B.Output FormatFor each test case, print the length of the smallest substring of B having all the characters of A, separated by newline. If no such substring is found, print -1.Constraints20 points1 <= T <= 1001 <= size(A), size(B) <= 10060 points1 <= T <= 1001 <= size(A), size(B) <= 1000120 points1 <= T <= 1001 <= size(A), size(B) <= 10000General Constraints'a' <= A[i], B[i] <= 'z'ExampleInput4fkqyu frqkzkruqmfqyuzlkygonmwvytbytn uqhmfjaqtgngcwkuzyamnerphfmwbloets lwbcrsfothplxseplrtbshbtstjloxsfdzpd dclzztpjldkndgbdqqzmbpOutput7-1139ExplanationTest Case 1:The smallest substring containing all characters of A is "fqyuzlk", which has a length of 7.Test Case 2:Despite considering all possible substrings of B, we cannot find any substring containing all characters of A.Test Case 3:The smallest substring containing all characters of A is "bcrsfothplxse", which has a length of 13.Test Case 4:The smallest substring containing all characters of A is "ztpjldknd", which has a length of 9.
Given a string S(input consisting) of ‘*’ and ‘#’. The length of the string is variable. The task is to find the minimum number of ‘*’ or ‘#’ to make it a valid string. The string is considered valid if the number of ‘*’ and ‘#’ are equal. The ‘*’ and ‘#’ can be at any position in the string.Note : The output will be a positive or negative integer based on number of ‘*’ and ‘#’ in the input string.(*>#): positive integer(#>*): negative integer(#=*): 0Example 1:Input 1:###*** -> Value of SOutput :0 ? number of * and # are equal
Problem StatementYou are given a string s of length n. You want to find all the distinct non-empty strings that can be formed from s such that:No two adjacent characters from the string s are chosen in the string that we make from s.Since the answer can be large print it modulo 109+7.Input FormatThe only line of input contains a string s.Constraints1 <= n <= 105Output FormatReturn an integer as asked.
Raju is preparing questions for the internal test. While creating questions, he gave one such question to his son Arun to solve. Raju has given the string S to his son Arun. Arun's task is to print the size of the longest possible substring that has exactly K unique characters.ExampleInput:String = aabacbebebe; K = 3Output:The substring will be cbebebe with length 7. Explanation:The unique characters in the string are: 'a', 'b', 'c', and 'e'. The longest subsequence with at most 3 distinct characters is "aabacbe". It contains the characters 'a', 'b', and 'c', which is the maximum number of distinct characters allowed (k = 3). Therefore, the length of the longest subsequence is 7.Input format :The first line of input consists of the string S.The second line of input consists of the integer K.Output format :The output prints the size of the longest possible substring that has exactly K unique characters.Refer to the sample output for the formatting specifications.Code constraints :1≤ string length ≤ 501≤ K ≤10Sample test cases :Input 1 :aabacbebebe3Output 1 :7Input 2 :abbc1Output 2 :2
Given a string of lowercase alphabets, count all possible substrings (not necessarily distinct) that have exactly k distinct characters. Example 1:Input:S = "aba", K = 2Output:3Explanation:The substrings are: "ab", "ba" and "aba".
Upgrade your grade with Knowee
Get personalized homework help. Review tough concepts in more detail, or go deeper into your topic by exploring other relevant questions.