Sponsored
Sponsored
The aim here is to transform the given string into either "010101..." or "101010...", as these are the only two possible alternating patterns for a binary string. By comparing the given string to these patterns, we can determine the minimum number of operations required.
We create these patterns for the length of the string and then count mismatches for both patterns by iterating through the string.
Time Complexity: O(n), where n is the length of the string, due to the single pass through the string.
Space Complexity: O(1), as only a constant amount of extra space is used.
1#include <stdio.h>
2#include <string.h>
3
4int minOperations(char *s) {
5 int len = strlen(s);
6 int pattern1 = 0, pattern2 = 0;
7 for (int i = 0; i < len; i++) {
8 if (s[i] != (i % 2 == 0 ? '0' : '1')) pattern1++;
9 if (s[i] != (i % 2 == 0 ? '1' : '0')) pattern2++;
10 }
11 return pattern1 < pattern2 ? pattern1 : pattern2;
12}
13
14int main() {
15 char s[] = "0100";
16 printf("%d\n", minOperations(s));
17 return 0;
18}The minOperations function calculates the number of operations needed to make the string alternating by comparing it to two alternating patterns: 010101... and 101010.... It iterates through the string and counts the mismatches for both patterns, returning the minimum of the two counts.
This method involves precomputing two mask strings that represent the possible alternating strings for any given length. We perform a comparison between the string and both masks, incrementing a counter for each mismatch, and outputting the smaller of the two.
Time Complexity: O(n).
Space Complexity: O(n) for mask storage.
1#include <iostream>
int minOperations(const std::string& s) {
int len = s.length();
std::string mask1(len, '0'), mask2(len, '1');
for (int i = 0; i < len; i++) {
mask1[i] = i % 2 == 0 ? '0' : '1';
mask2[i] = i % 2 == 0 ? '1' : '0';
}
int count1 = 0, count2 = 0;
for (int i = 0; i < len; i++) {
if (s[i] != mask1[i]) count1++;
if (s[i] != mask2[i]) count2++;
}
return std::min(count1, count2);
}
int main() {
std::string s = "0100";
std::cout << minOperations(s) << std::endl;
return 0;
}This solution constructs two strings (masks) that represent the two patterns for binary alternation. It then counts mismatches with the original string and returns the fewest mismatches.