Check if N sized String with given number of 00, 01, 10, 11 Substrings exists

Given an integer N and four values a, b, c, d (where a ≥ 0, b ≥ 0, c ≥ 0, d ≥ 0), the task is to check if it is possible to create a binary string of length N such that:

• There are exactly a substrings of “00” 
• There are exactly b substrings of “01”
• There are exactly c substrings of “10”
• There are exactly d substrings of “11”

Examples:

Input:  N = 11, a = 2, b = 3, c = 3, d = 2
Output : Yes 
Explanation : In this string, exactly 2 numbers of 00, exactly 3 numbers 01, exactly 3 numbers of 10 and exactly 2 numbers of 11.

Input : N = 11, a = 0, b = 3, c = 3, d = 0
Output: No 
Explanation : We can make a string with exactly 3 numbers of 01 and 3 numbers of 10, but string size will be 7, so can’t possible to make a perfect binary string with 11 length.

Input: N = 4, a = 1, b = 0, c = 0, d = 1
Output: No
Explanation : We can’t make a string because if 00 are there and 11 are there, it is must that 01 or 10 will be there in junction of 00 and 11  

Observation:

We have to check the cases where string can’t be formed.

• Case 1: when number of  01 and 10 pairs are zero, then it can’t be possible to create a string if 00 and 11 pairs appears non-zero times. Because, these are required to form  a 01 or 10 in the junction of 00 and 11.
• Case 2: when b and c are the number of  01 and 10 pairs, then it is not possible to create a string if abs(b-c)>1.
• Case 3: If case 1 and case 2 are not happening and string is formed with exact pairs of 00, 11, 10, 01 and if the length of the string is not equal to n, then the string is not possible.

Approach: Follow the below approach to solve the problem:

• Check if 01 and 10 appear zero times and 00 and 11 appear non-zero times then it is not possible to create such binary string.
• Check if the absolute difference between numbers 01 and 10 is:
  • Greater than 1, abs(b – c) > 1, then it is not possible to create a string.
  • Equal to 1, calculate the length of the string, if it is equal to n, return true, else return false.
  • Equal to 0, calculate the length of the string, if it is equal to n, return true, else return false.

Steps were to follow the above approach:

• Initialize a variable say, sum = 0 to calculate the length of the string.
• Check if b == 0 && c == 0 && d != 0 && a != 0, then it is not possible to create a perfect binary string, return false.
• Check if abs(b – c) > 1, then it is not possible to create a perfect binary string, return false.
• Check if abs(b – c) == 1, and calculate the length of the string, by updating the sum
  • Add max(b, c) * 2 to sum
  • Add ‘a’ to sum
  • Add ‘d’ to the sum
  • Increment sum by 1.
• Check if sum != n, return false, else return true.
• Check if b == c, calculate the length of the string, and check if sum != n, return false, else return true.

Below is the implementation for the above approach:

Time Complexity: O(1)
Auxiliary Space: O(1)

Given an integer N and four values a, b, c, d (where a ≥ 0, b ≥ 0, c ≥ 0, d ≥ 0), the task is to check if it is possible to create a binary string of length N such that:

• There are exactly a substrings of “00” 
• There are exactly b substrings of “01”
• There are exactly c substrings of “10”
• There are exactly d substrings of “11”

Examples:

Input:  N = 11, a = 2, b = 3, c = 3, d = 2
Output : Yes 
Explanation : In this string, exactly 2 numbers of 00, exactly 3 numbers 01, exactly 3 numbers of 10 and exactly 2 numbers of 11.

Input : N = 11, a = 0, b = 3, c = 3, d = 0
Output: No 
Explanation : We can make a string with exactly 3 numbers of 01 and 3 numbers of 10, but string size will be 7, so can’t possible to make a perfect binary string with 11 length.

Input: N = 4, a = 1, b = 0, c = 0, d = 1
Output: No
Explanation : We can’t make a string because if 00 are there and 11 are there, it is must that 01 or 10 will be there in junction of 00 and 11  

Observation:

We have to check the cases where string can’t be formed.

• Case 1: when number of  01 and 10 pairs are zero, then it can’t be possible to create a string if 00 and 11 pairs appears non-zero times. Because, these are required to form  a 01 or 10 in the junction of 00 and 11.
• Case 2: when b and c are the number of  01 and 10 pairs, then it is not possible to create a string if abs(b-c)>1.
• Case 3: If case 1 and case 2 are not happening and string is formed with exact pairs of 00, 11, 10, 01 and if the length of the string is not equal to n, then the string is not possible.

Approach: Follow the below approach to solve the problem:

• Check if 01 and 10 appear zero times and 00 and 11 appear non-zero times then it is not possible to create such binary string.
• Check if the absolute difference between numbers 01 and 10 is:
  • Greater than 1, abs(b – c) > 1, then it is not possible to create a string.
  • Equal to 1, calculate the length of the string, if it is equal to n, return true, else return false.
  • Equal to 0, calculate the length of the string, if it is equal to n, return true, else return false.

Steps were to follow the above approach:

• Initialize a variable say, sum = 0 to calculate the length of the string.
• Check if b == 0 && c == 0 && d != 0 && a != 0, then it is not possible to create a perfect binary string, return false.
• Check if abs(b – c) > 1, then it is not possible to create a perfect binary string, return false.
• Check if abs(b – c) == 1, and calculate the length of the string, by updating the sum
  • Add max(b, c) * 2 to sum
  • Add ‘a’ to sum
  • Add ‘d’ to the sum
  • Increment sum by 1.
• Check if sum != n, return false, else return true.
• Check if b == c, calculate the length of the string, and check if sum != n, return false, else return true.

Below is the implementation for the above approach:

Time Complexity: O(1)
Auxiliary Space: O(1)