Problem Statement

You are given a target binary string of length n. Initially, you also have another string str of length n containing all 0s. You need to make str equal to the target by performing some number of operations.

In one operation, you can take an index i where 0 <= i < n and flip all bits in the inclusive range [i, n - 1]. Here, Flip means changing '1' to '0' and '0' to '1'.

Return the minimum number of operations required to make string str equal to target.

Examples

• Example 1:

  • Input: target = "001"
  • Expected Output: 1
  • Justification: Flipping the last character in the str string from 0 to 1 will make the string "001", achieving the goal in one operation.

• Example 2:

  • Input: target = "11001"
  • Expected Output: 3
  • Justification: Starting with s as "00000", the process to make s equal to "11001" is as follows:
    1. Flip the last three digits to get "00111".
    2. Flip all five digits to get "11000".
    3. Flip the last digit to get "11001". This process requires three operations, thus the expected output is 3.

• Example 3:

  • Input: target = "100010"
  • Expected Output: 4
  • Justification: Beginning with s as "000000", to transform s into "100010", the sequence of operations could be:
    1. Flip the last two digits to get "000011".
    2. Flip the last digit to get "000010".
    3. Flip all six digits to get "111101".
    4. Flip the last five digits to get "100010". This sequence involves four operations, making the expected output 4.

Try it yourself

Try solving this question here: