String Without 000 Or 111

Easy

0/40

Average time to solve is 15m

Contributed by

27 upvotes

Asked in company

Problem statement

You have to create any binary string ‘S’ of length ‘M+N’ which has exactly ‘M’ 0’s and ‘N’ 1’s. S can not have ‘111’ or ‘000’ as a substring.

Given ‘M’ and ‘N’ it is guaranteed that there exists at least one binary string ‘S’.

The substring of a string is obtained by deleting characters from the start and end of the string.

For example:

M = 6, N = 6
ANS = “110011001100”

In ans no three consecutive characters are same. 
ANS=”001100110011” is also a valid answer.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line of input contains an integer 'T’ denoting the number of test cases to run. Then the test case follows.

The first line and the only line of each test case contain two space-separated integers ‘M’ and ‘N’.

Output Format:

For each test case print any binary string ‘S’ satisfying all the conditions.

Note:

You don’t need to print anything. It has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 10
1 <= M+N <= 5000 

Time Limit: 1 sec

Sample Input 1:

2
4 1
4 2

Sample Output 1:

00100
001100

Explanation For Sample Input 1:

For the first test case, there is only one correct binary string ‘00100’ 

For the second test case “001100”, “010100”, “100100‘ etc all are valid.

Sample Input 2:

2
4 6
7 5

Sample Output 2:

1101101010
001010101010

Hint 1

If we create the string from left to right, For a new character It is always good to add the character which is more common and can be added. can we create ‘S’ using this strategy ??

Approaches (1)

Approach 1

Greedy

We will iterate from left to right and check for the remaining numbers of 1’s and 0’s to be added and check if it can be added without violating the constrain.

The algorithm will be-

ANS = []
While (N + M > 0)
- If M > N
  - If ans.size() > 1 and ans[ans.size() - 1] == ans[ans.size() - 2] == ’0’
    - If last two characters are equal to ‘0’ than we can not Add ‘0’
    - ANS.append(‘1’)
    - N -= 1
  - Else
    - ANS.append(‘0’)
    - M -= 1
- Else
  - If ans.size() > 1 and ans[ans.size() - 1] == ans[ans.size() - 2] == ’1’
    - If last two characters are equal to ‘1’ than we can not Add ‘1’
    - ANS.append(‘0’)
    - M -= 1
  - Else
    - Adding the most common character
    - ANS.append(‘1’)
    - N -= 1
Return concatination_of(ANS)

Time Complexity

O(N + M) where M is the number of 0’s and N is the number of 1’s.

We will create the string from left to right adding one character at a time.

Space Complexity

O(N + M) where M is the number of 0’s and N is the number of 1’s.

Space required to store the final answer.

(100% EXP penalty)

String Without 000 Or 111

Console