Maximum count of characters that can replace ? by at most A 0s and B 1s with no adjacent duplicates

The aim of this article is to implement a program maximum count of characters that can replace? by at most A 0s and B 1s with no adjacent duplicates.

Given a couple of integers A and B, both of which that represent the number of 0s and 1s that are accessible, and a string Str with only the special characters "*" and "?" The aim is to determine the greatest number of characters that may be used in the '?' position without causing any neighboring characters to be identical.

Example 1

 Let us give the input string str = "*??*??*", A = 5, B = 2 Output obtained is : 4 

Explanation

You can change the string to "*01*01*". Therefore, (2 + 2 = 4) characters are the most that can be used in the location of "?"

Example 2

 Let us give the input string str = "*??*???*", A = 5, B = 0 Output obtained is : 3 

Explanation

You can change the string to "*0?*0?0*". Therefore, (1 + 2 = 3) characters are the most that can be used in the location of "?"

Example 3

 Let us give the input string str = "*??*??*", A = 0, B = 2 Output obtained is : 2 

Explanation

You can change the string to "*?1*?1*". Therefore, (1 + 1 = 2) characters are the most that can be used in the location of "?"

Problem Statement

Implement a program to find Maximum count of characters that can replace ? by at most A 0s and B 1s with no adjacent duplicates

Algorithm

The algorithm to find the Maximum count of characters that can replace ? by at most A 0s and B 1s with no adjacent duplicates given below

• Step 1 Define a Function to determine the maximum count of characters "A" and "B," which can fit in the position of "?"

• Step 2 Define a string str and the variable l is defined as the size or length of the string.

• Step 3 Define an integer variable current.

  The variable current is defined to Store the current or the present count of '?'s and it //is set to zero

• Step 4 Define an array segLengths[] in order to store the lengths of adjacent segments of '?'s

• Step 5 Traverse the string and check if the character is ??'. If so then, increment the current variable by 1

• Step 6 check whether current is equal to 0 or not. If not, then we have to re-initialize the current variable to zero

• Step 7 Define an integer Variable for storing the maximum count

• Step 8 define an integer variable "halfX" to store half of each elements in the array named segLengths[]

• Step 9 define an integer variable "halfY" to store half of each element with its remainder

• Step 10 If aCount is greater than bCount, then increment the maxCount by minimum of aCount and halfX

• Step 11 Update the aCount

• Step 12 Increment the maxCount by minimum of bCount and halfY

• Step 13 Update the bCount

• Step 14 Return the maxCount obtained

Example (C Program)

Here is the C program implementation of the above written algorithm to find the maximum count of characters that can replace ? by at most A 0s and B 1s with no adjacent duplicates.

 #include <stdio.h> #include <string.h> int maximumChar(char *str, int aCount, int bCount){ int l = strlen(str); int current = 0; int segLengths[100]; int segCount = 0; for (int i = 0; i < l; i++) { if (str[i] == '?') { current++; } else { if (current != 0) { segLengths[segCount++] = current; current= 0; } } } if (current != 0) { segLengths[segCount++] = current; } int maxCount = 0; for (int i = 0; i < segCount; i++) { int halfX = segLengths[i] / 2; int halfY = segLengths[i] / 2 + segLengths[i] % 2; if (aCount > bCount) { int temp = aCount; aCount = bCount; bCount = temp; } maxCount += (aCount < halfX ? aCount : halfX); aCount -= (aCount < halfX ? aCount : halfX); maxCount += (bCount < halfY ? bCount : halfY); bCount -= (bCount < halfY ? bCount : halfY); } return maxCount; } int main(){ char str[] = "*??*??*"; int aCount = 5, bCount = 2; printf("%d
", maximumChar(str, aCount, bCount)); return 0; } 

Output

On execution, it will produce the following output

 4 

Conclusion

Likewise we can find the Maximum count of characters that can replace ? by at most A 0s and B 1s with no adjacent duplicates. The challenge of obtaining the program to find the Maximum count of characters that can replace ? by at most A 0s and B 1s with no adjacent duplicates" is resolved in this article. Here C programming code as well as the algorithm to find the Maximum count of characters that can replace ? by at most A 0s and B 1s with no adjacent duplicatesare provided.