FastPrep
Problem · String

Minimum Flips to Alternate Binary String (With K Flip Window)

Learn this problem
● HardGoogleNEW GRADOA
See Google hiring insights

Problem statement

You are given a binary string s. In one operation, you can flip a subarray of length exactly k (flip all bits in that subarray). Return the minimum number of such operations needed to make the string alternating (i.e., no two adjacent bits are the same). If it's not possible, return -1.

Function

minFlips(s: String, k: int) → int

Examples

Example 1

s = "00010111"k = 3return = 6
The target 01010101 is unreachable with length-3 flips. To reach 10101010, the leftmost mismatch forces flips starting at indices 0, 1, 2, 3, 4, and 5, for 6 operations. Exhaustive state search confirms that no shorter sequence exists.

Constraints

  • 1 ≤ s.length ≤ 2 * 10^5
  • s[i] is 0 or 1.
  • 1 ≤ k ≤ s.length
  • Every operation flips exactly k consecutive bits.

More Google problems

drafts saved locally
public int minFlips(String s, int k) {
  // write your code here
}
s"00010111"
k3
expected6
checking account