#1529

Minimum Suffix Flips

pupil · 510 · lc medium +27 · verified · 73.9% accepted · 1,070 likes · top 84%

Description

Starting with a binary string s of length n set to all '0's, you may repeatedly choose an index i and flip every bit in s[i..n-1]. Return the minimum number of such suffix-flip operations needed to transform s into the given binary string target.

Example 1:

Input: target = "10111"

Output: 3

Explanation: Initially, s = "00000".

Choose index i = 2: "00000" -> "00111"

Choose index i = 0: "00111" -> "11000"

Choose index i = 1: "11000" -> "10111"

We need at least 3 flip operations to form target.

Example 2:

Input: target = "101"

Output: 3

Explanation: Initially, s = "000".

Choose index i = 0: "000" -> "111"

Choose index i = 1: "111" -> "100"

Choose index i = 2: "100" -> "101"

We need at least 3 flip operations to form target.

Example 3:

Input: target = "00000"

Output: 0

Explanation: We do not need any operations since the initial s already equals target.

Code

1

2

3

class Solution:
    def minFlips(self, target: str) -> int:

class Solution:
    def minFlips(self, target: str) -> int: