23.01.17 Today’s Leetcode

926. Flip String to Monotone Increasing

1 이 시작되는 index를 찾는것이 이 문제의 핵심이다. 가장 최소의 flip number을 구해야 하기 때문에, 이 index를 찾는게 생각보다 까다로운데 차근차근히 생각해보면 쉽다. index 기준으로 왼쪽에 있는 1의 갯수와 오른쪽에 있는 0의 갯수가 가장 작을 때가 minimum flip을 위한 최적의 index이다. 왼쪽에 있는 1을 모두 뒤집어야 하고, 오른쪽에 있는 0을 모두 뒤집어야 하기 때문이다.

class Solution:
    def minFlipsMonoIncr(self, s: str) -> int:
        n = len(s)
        if n == 1:
            return 0
        one_counter = [0] * n
        zero_counter = [0] * n
        # zero_counter[i] means that # of '1' between s[:i]
        # one_counter[i] means that # of '1' between s[i:]

        one_counter[0] = (1 if s[0] == '1' else 0)
        zero_counter[n - 1] = (1 if s[n - 1] == '0' else 0)
        for i in range(1, n):
            one_counter[i] = one_counter[i - 1] + (1 if s[i] == '1' else 0)
        for i in range(n - 2, -1, -1):
            zero_counter[i] = zero_counter[i + 1] + (1 if s[i] == '0' else 0)
        
        res = 10**9
        for i in range(n):
            res = min(res, one_counter[i] + zero_counter[i] - 1)
        return res