Sponsored
Sponsored
To make the binary string beautiful, we need to ensure that each pair of adjacent characters forms a part of a longer sequence of identical numbers. For instance, if there is '10' or '01', we can choose to change one of the characters to make the pair '11' or '00'. We will count how many changes are needed to make all pairs in the desired format.
Since the string length is even, we can consider every odd index with its preceding even index in the string. We will check how many such pairs would need to be changed either to '00' or '11'. The sum of these changes will be our answer.
Time Complexity: O(n), where n is the length of the string. We make a single pass through the string, examining pairs of characters.
Space Complexity: O(1), only a few variables are used for counting.
1#include <stdio.h>
2#include <string.h>
3
4int minChangesToBeautiful(char *s) {
5 int length = strlen(s);
6 int changes = 0;
7 for (int i = 0; i < length; i += 2) {
8 if (s[i] != s[i+1]) {
9 changes++;
10 }
11 }
12 return changes;
13}
14
15int main() {
16 char s[] = "1001";
17 int result = minChangesToBeautiful(s);
18 printf("%d\n", result);
19 return 0;
20}The function minChangesToBeautiful takes a binary string as input and computes the number of changes required to make it beautiful by counting adjacent different pairs. For each such pair found, it increments a change counter. This is based on pairing every two consecutive numbers in the string and checking if they are different.
This approach utilizes a sliding window that calculates the cumulative changes required to transform each segment of the string into either '00' or '11'. While iterating over pairs of characters, we check the discrepancy from '00' alternations and '11' alternations. To achieve this, two patterns are monitored: one representing making all pairs '00' and the other '11'. The minimum between these two paths will give the total minimum steps needed.
Time Complexity: O(n), where n is the length of the string, involving one linear iteration over the data.
Space Complexity: O(1), requiring no additional space except variables.
1public class BinaryString {
2 public static int minChangesToBeautiful(String s) {
3 int changesPattern1 = 0, changesPattern2 = 0;
4 for (int i = 0; i < s.length(); i++) {
5 if (i % 2 == 0) {
6 if (s.charAt(i) != '0') changesPattern1++;
7 if (s.charAt(i) != '1') changesPattern2++;
8 } else {
9 if (s.charAt(i) != '1') changesPattern1++;
10 if (s.charAt(i) != '0') changesPattern2++;
11 }
12 }
13 return Math.min(changesPattern1, changesPattern2);
14 }
15
16 public static void main(String[] args) {
17 String s = "1001";
18 System.out.println(minChangesToBeautiful(s));
19 }
20}This Java solution evaluates two alternating patterns, incrementally counting deviations from each, and outputs the fewer transformations required, by optimally realigning characters based on initial setups.