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.
1public class AlternatingString {
2 public static int minOperations(String s) {
3 int pattern1 = 0, pattern2 = 0;
4 for (int i = 0; i < s.length(); i++) {
5 if (s.charAt(i) != (i % 2 == 0 ? '0' : '1')) pattern1++;
6 if (s.charAt(i) != (i % 2 == 0 ? '1' : '0')) pattern2++;
7 }
8 return Math.min(pattern1, pattern2);
9 }
10
11 public static void main(String[] args) {
12 String s = "0100";
13 System.out.println(minOperations(s));
14 }
15}This Java implementation checks the string against both expected alternating patterns, using the Math.min() function to return the minimum operations required to achieve either pattern.
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
This solution creates two masks in Java using StringBuilder to generate both 0101 and 1010 patterns. The mismatches with the original string are then calculated to find the minimum operations needed.