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

In this problem, we need to replace '?' characters in a string with '0's and '1's such that no two adjacent characters are the same, while maximizing the number of replacements using at most A zeros and B ones.

Syntax

int maximumChar(char *str, int aCount, int bCount);

Problem Statement

Given a string containing '*' and '?' characters, and two integers A and B representing available 0s and 1s, find the maximum number of '?' characters that can be replaced without creating adjacent duplicates.

Algorithm

The approach involves the following steps

• Step 1 Identify contiguous segments of '?' characters in the string
• Step 2 For each segment of length n, calculate how many 0s and 1s are needed
• Step 3 In alternating pattern, we need ceil(n/2) of one type and floor(n/2) of another
• Step 4 Greedily assign the smaller count first to maximize total replacements
• Step 5 Sum up all possible replacements across segments

Example 1: Basic Case

Let's implement the solution for the given problem

#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;
    
    // Find segments of consecutive '?' characters
    for (int i = 0; i < l; i++) {
        if (str[i] == '?') {
            current++;
        } else {
            if (current != 0) {
                segLengths[segCount++] = current;
                current = 0;
            }
        }
    }
    
    // Handle last segment if string ends with '?'
    if (current != 0) {
        segLengths[segCount++] = current;
    }
    
    int maxCount = 0;
    
    // Process each segment
    for (int i = 0; i < segCount; i++) {
        int halfX = segLengths[i] / 2;
        int halfY = segLengths[i] / 2 + segLengths[i] % 2;
        
        // Ensure aCount is the smaller value for greedy approach
        if (aCount > bCount) {
            int temp = aCount;
            aCount = bCount;
            bCount = temp;
        }
        
        // Use smaller count first
        int usedA = (aCount < halfX) ? aCount : halfX;
        maxCount += usedA;
        aCount -= usedA;
        
        // Use remaining larger count
        int usedB = (bCount < halfY) ? bCount : halfY;
        maxCount += usedB;
        bCount -= usedB;
    }
    
    return maxCount;
}

int main() {
    char str[] = "*??*??*";
    int aCount = 5, bCount = 2;
    
    printf("String: %s<br>", str);
    printf("Available 0s: %d, Available 1s: %d<br>", aCount, bCount);
    printf("Maximum replacements: %d<br>", maximumChar(str, aCount, bCount));
    
    return 0;
}

String: *??*??*
Available 0s: 5, Available 1s: 2
Maximum replacements: 4

Example 2: Edge Case with Limited Resources

Testing with different constraints

#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;
        }
        
        int usedA = (aCount < halfX) ? aCount : halfX;
        maxCount += usedA;
        aCount -= usedA;
        
        int usedB = (bCount < halfY) ? bCount : halfY;
        maxCount += usedB;
        bCount -= usedB;
    }
    
    return maxCount;
}

int main() {
    // Test case with limited 1s
    char str1[] = "*??*???*";
    printf("Test 1 - String: %s, A=5, B=0<br>", str1);
    printf("Result: %d<br><br>", maximumChar(str1, 5, 0));
    
    // Test case with limited 0s
    char str2[] = "*??*??*";
    printf("Test 2 - String: %s, A=0, B=2<br>", str2);
    printf("Result: %d<br>", maximumChar(str2, 0, 2));
    
    return 0;
}

Test 1 - String: *??*???*, A=5, B=0
Result: 3

Test 2 - String: *??*??*, A=0, B=2
Result: 2

Key Points

• The algorithm works by identifying segments of consecutive '?' characters
• For a segment of length n, we need ceil(n/2) of one type and floor(n/2) of another type to avoid adjacent duplicates
• Greedy approach ensures we use available resources optimally
• Time complexity is O(n) where n is string length

Conclusion

This solution efficiently finds the maximum number of '?' characters that can be replaced while maintaining the constraint of no adjacent duplicates. The greedy approach ensures optimal use of available 0s and 1s.