Fewest append-to-end moves to reverse a binary image

0
Sign in

An image is stored as a binary string s: '1' is a white pixel and '0' is a black pixel. To make a backup, you want to turn s into its reverse, s read from right to left.

You may use one operation any number of times: pick any character of the current string, remove it, and append it at the end.

Implement find_minimum_operations(s: str) -> int. It returns the fewest operations that turn s into its reverse.

Constraints

  • 0 <= len(s) <= 2 * 10^5
  • s contains only '0' and '1'

Example 1

s = "0010"      reverse = "0100"
move index 1 ('0'): "010" + "0" = "0100"
output: 1

Example 2

s = "0001"      reverse = "1000"
output: 3

Only the final '1' can stay where it is relative to the rest. All three '0's have to be moved behind it.

Example 3

s = "0110"      output: 0   (s is already a palindrome)
AmazonCodingMedium

Sign in to see the worked answer

The full answer, chapter by chapter, with what interviewers expect at each level. Free with an account: one full answer per company.