Tester: Kevin Atienza
Editorialist: Ajay K. Verma
Russian Translator: Sergey Kulik
Mandarian Translator: Gedi Zheng
Given a binary string and an integer k, flip the smallest number of characters of the string, such that the resulting string has no more than k consecutive equal characters.
Handle the case of k = 1, and k > 1 separately. In case of k = 1, the resulting string must have alternating characters, and there are only two such strings (one starting with 0, and the other starting with 1), pick the one which can be obtained by fewer flips. In case of k > 1, partition the original string into substrings made of the same character. If a substring is of length n > k, then flip \lfloor n/(k + 1) \rfloor characters in this substring, so that it contains no more than k consecutive equal characters. Special care must be taken when n is divisible by k + 1
We are given a binary string S and an integer k. The task is to flip the minimum number of characters of the given string such that resulting string has no more than k consecutive equal characters.
Let us split the string S into substrings such that all characters of a substring are the same, e.g., if the original string was “1100000011100101”, then the partition would have 7 substrings: “11”, “000000”, “111”, “00”, “1”, “0”, and, “1”. Now, any substring which has a length greater than k, will require some flips, so that after flip we can further split this substring into smaller substrings of equal characters, and of length not exceeding k.
For example, if a substring is “000000000”, and the value of k is 3, then we need to make two flips into this substring to convert it into “000100010”, which can then be split into “000”, “1”, “000”, “1”, “0”, none of which have a length higher than k = 3.
In fact, if a substring is of length n, then we need to make exactly \lfloor n/(k + 1) \rfloor flips to break it into substrings of length not exceeding k (we flip each (k + 1)-th character of the substring). However, there is one tricky case, when n is divisible by (k + 1). In this case, we would end up flipping the last character of the substring, which would increase the length of the substring following this substring. For example:
original string: “00011”, k = 2,
substrings: “000”, “11”
After flip: “001”, “11”
After merging back: “00111”
The final string still has 3 equal consecutive characters. Hence, we must make sure that we never flip the last character of a substring. This can always be achieved when k > 1, as instead of the last character, we would flip the second last character of the string, and it will not interfere with the next substring. For example,
original string: “1100000011100101”, k = 2,
substrings: “11”, “000000”, “111”, “00”, “1”, “0”, “1”,
after flip: “11”, “001010”, “101”, “00”, “1”, “0”, “1”,
after merger: “1100101010100101”
Note that, in the flip step, we flipped the second last character of second and third substring, instead of the last one. However, this is not possible in case k = 1, because if we flip the second last character, then it will interfere with the previous substring.
Special Handling of k = 1:
In case of k = 1, there can no two consecutive equal characters in the resulting string, i.e., resulting string must have alternating characters. There are only two such strings of length N: one which starts with “0” and then alternates between “0” and “1”, and the other which starts with “1”, and then alternates. We consider both of these as potential target string, and pick the one which could be obtained by using fewer flips.