Fewest Flips to Split a Binary String into Blocks
Hudson River Trading● EasyFULLTIMEOAProblem statement
You are given a binary string s and two integers k and m.
Cut s into blocks of exactly k characters. The first block is the first k characters, the next block is the next k characters, and so on, with no gaps and no overlaps. The split works when every block holds exactly m ones.
In one flip, you change one character of s from '0' to '1', or from '1' to '0'.
Return the fewest flips needed to make the split work. Return 0 if it already works. If the length of s is not a multiple of k, the string cannot be cut into blocks of size k at all, so return -1.
Function
minFlipsToSplit(s: String, k: int, m: int) → intExamples
Example 1
s = "110100"k = 3m = 2return = 1The blocks are "110" and "100". The first block already has two ones. The second block has one, so it needs one flip, for example turning "100" into "110". The answer is 1.
Example 2
s = "011010"k = 2m = 1return = 0The blocks are "01", "10" and "10". Each one holds exactly one 1, so the split already works and no flips are needed.
Example 3
s = "1010"k = 3m = 1return = -1The length of s is 4, which is not a multiple of 3. The string cannot be cut into blocks of size 3, so the answer is -1.
Constraints
1 <= s.length <= 10^5scontains only the characters'0'and'1'.1 <= k <= 10^50 <= m <= k