Link: https://leetcode.com/problems/minimum-suffix-flips/
Solution:
Topics: greedy
Intuition
This is kind of an annoying problem that is way less complicated than it appears on first glance. The idea is to track the status of the remaining bits in our created string (we don’t actually have to create the string). When the status of the current bit in s differs from the current bit in target, we make a flip and update the status of the remaining bits in s.
For example:
00000 #s
10111 #target
At index 0, the status of s is 0, target is 1. We flip
11111 #s
10111 #target
At index 1, the status of s is 1, target is 0. We flip
10000 #s
10111 #target
At index 2, the status of s is 1, target is 0. We flip
10111 #s
10111 #target
s == target, 3 flips were made. At no point were we required to sore more than the current status of s.
Implementation
def min_flips(target):
flips = 0
s_status = '0'
for bit in target:
if s_status != bit:
flips += 1
s_status = bit
return flips
#time: o(n)
#memory: o(1)Visual
Review 1
Very easy medium. Not much to say about this one.