You are given a positive integer n.A binary string x is valid if all substrings of x of length 2 contain at least one "1".Return all valid strings with length n, in any order. Example 1:Input: n = 3Output: ["010","011","101","110","111"]Explanation:The valid strings of length 3 are: "010", "011", "101", "110", and "111".Example 2:Input: n = 1Output: ["0","1"]Explanation:The valid strings of length 1 are: "0" and "1".
Question
You are given a positive integer n.A binary string x is valid if all substrings of x of length 2 contain at least one "1".Return all valid strings with length n, in any order. Example 1:Input: n = 3Output: ["010","011","101","110","111"]Explanation:The valid strings of length 3 are: "010", "011", "101", "110", and "111".Example 2:Input: n = 1Output: ["0","1"]Explanation:The valid strings of length 1 are: "0" and "1".
Solution 1
Here is a Python solution using recursion:
def valid_strings(n):
if n == 1:
return ["0", "1"]
else:
result = []
for s in valid_strings(n - 1):
if s[-1] == "1":
result.append(s + "0")
result.append(s + "1")
else:
result.append(s + "1")
return result
This function works by first checking if n is 1. If it is, it returns the list ["0", "1"] because these are the only valid strings of length 1.
If n is not 1, the function calls itself with n - 1 to get all valid strings of length n - 1. It then appends either "0" or "1" to each of these strings to create valid strings of length n.
The function checks the last character of each string of length n - 1. If the last character is "1", it can append either "0" or "1" to create a valid string of length n. If the last character is "0", it can only append "1" to create a valid string of length n.
Finally, the function returns the list of all valid strings of length n.
Solution 2
Here is a Python solution using recursion:
def find_valid_strings(n):
if n == 1:
return ["0", "1"]
else:
result = []
for s in find_valid_strings(n - 1):
result.append(s + "1")
if s[-1] != "0":
result.append(s + "0")
return result
This function works by first checking if n is 1. If it is, it returns the list ["0", "1"] because these are the only valid strings of length 1.
If n is not 1, the function recursively calls itself with n - 1. It then iterates over each string s in the result of this recursive call. For each string s, it appends s + "1" to the result list because adding a "1" to the end of any string always results in a valid string.
The function also checks if the last character of s is not "0". If it's not, it appends s + "0" to the result list. This is because adding a "0" to the end of a string is only valid if the string does not already end with a "0". This ensures that all substrings of length 2 contain at least one "1".
Finally, the function returns the result list, which contains all valid strings of length n.
Similar Questions
Given a binary representation in the form of a string(s) of a number n, the task is to find a binary representation of n+1.Note: Output binary string should not contain leading zeros.Example 1:Input: s = "10"Output: 11Explanation: "10" is the binary representation of 2 and binary representation of 3 is "11"Example 2:Input: s = "111"Output: 1000Explanation: "111" is the binary representation of 7 and binary representation of 8 is "1000"Your Task: You don't need to read input or print anything. Complete the function binaryNextNumber()which takes s as input parameter and returns the string.Expected Time Complexity: O(n)Expected Auxiliary Space: O(n) to store resultant string Constraints:1 <= n <= 105
You are given a binary string s that contains at least one '1'.You have to rearrange the bits in such a way that the resulting binary number is the maximum odd binary number that can be created from this combination.Return a string representing the maximum odd binary number that can be created from the given combination.Note that the resulting string can have leading zeros.
ow many binary strings of length 8 are there that contain two or fewer 1s?
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
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
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.