aboutsummaryrefslogtreecommitdiff
path: root/min_flips_bin_string.c
blob: d3eef062a3c5e82e62a5ad410effa025fb1d2b80 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
// 1888. Minimum Number of Flips to Make the Binary String Alternating
#include <limits.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/*
 * you are given a binary string 's'. you are allowed to perform two types of
 * operations on the string in any sequence: 1: remove the character at the
 * start of the string 's' and append it to the end of the string. 2: pick any
 * characters in 's' and flip its value, ie. if its value is 0 it becomes 1 and
 * vice versa. return the minimum number of type-2 operations needed to perform
 * such that 's' becomes alternating. the string is called alternating if no two
 * adjacent characters are equal. for example, the strings "010" and "1010" are
 * alternating, while the string "0110" is not.
 */

int minFlips(char *s) {
  int n = strlen(s), idx = 0, min_ops = INT_MAX, diff1 = 0, diff2 = 0, left = 0,
      right = 0;
  char *g_str = calloc(1, 2 * n + 1);
  char *z_tar = calloc(1, 2 * n + 1);
  char *o_tar = calloc(1, 2 * n + 1);
  strcat(g_str, s);
  strcat(g_str, s);
  for (int i = 0; i < 2 * n; i++) {
    z_tar[idx] = i % 2 ? '1' : '0';
    o_tar[idx++] = i % 2 ? '0' : '1';
  }
  while (right < 2 * n) {
    diff1 += g_str[right] != z_tar[right];
    diff2 += g_str[right] != o_tar[right];
    if (right - left + 1 > n) {
      if (g_str[left] != z_tar[left])
        diff1--;
      if (g_str[left] != o_tar[left])
        diff2--;
      left++;
    }
    if (right - left + 1 == n)
      min_ops = fmin(min_ops, fmin(diff1, diff2));
    right++;
  }
  return min_ops;
}

int main() {
  char s1[] = {"111000"}, s2[] = {"010"}, s3[] = {"1110"};
  printf("%d\n", minFlips(s1)); // expect: 2
  printf("%d\n", minFlips(s2)); // expect: 0
  printf("%d\n", minFlips(s3)); // expect: 1
}