[leetcode #926] Flip String to Monotone Increasing

Problem

A binary string is monotone increasing if it consists of some number of 0's (possibly none), followed by some number of 1's (also possibly none).

You are given a binary string s. You can flip s[i] changing it from 0 to 1 or from 1 to 0.

Return the minimum number of flips to make s monotone increasing.

Example 1:

Input: s = "00110"
Output: 1
Explanation: We flip the last digit to get 00111.

Example 2:

Input: s = "010110"
Output: 2
Explanation: We flip to get 011111, or alternatively 000111.

Example 3:

Input: s = "00011000"
Output: 2
Explanation: We flip to get 00000000.

Constraints:

・ 1 <= s.length <= 105
・ s[i] is either '0' or '1'.    

Idea

문제를 처음 보는 순간 쉽게 풀 수 있겠다라는 생각을 했는데 제출한 답이 어디선가 틀려버렸다. 분하다. Medium 난이도 문제도 제대로 못 풀어서야 어디 이직이나 할 수 있겠는가. 별 생각없이 풀 경우 edge case를 코드 이 곳 저 곳에 넣는 경우가 많은데, 이 문제도 마찬가지였다. 틀린 case를 보고 "edge case구나~"하고 코드를 여기저기 넣는 순간 그 날의 leetcode는 망한 거라고 보면 된다. 🥲

자정이 넘어서 풀이를 볼 수밖에 없었는데 생각보다 간단하게 풀 수 있어서 놀랐다. array에서 ith index에서 jth index까지 합을 구하라고 할 때 반복해서 array를 탐색하지 않는 방법 중 하나가 running sum이다. running sum의 원리를 Monotone string을 구할 때도 사용할 수 있다. 0과 1로만 구성된 binary string에서 ith index에서 jth index까지 0 또는 1의 개수를 구할 때 running sum을 적용할 수 있는 것이다.

string을 구성하는 각 character를 처음부터 탐색한다고 가정하자. string의 길이가 n일 때 n+1 크기의 array를 먼저 만들고, 해당 array가 저장하는 값을 0번째 문자에서 i번째 문자로 이루어져있는 substring이 가지고 있는 1의 개수로 정한다. 그럼 i번째 문자에서 j번째까지 문자로 이루어진 substring이 가지고 있는 1의 개수와 0의 개수는 다음과 같다.

P → 1의 개수를 저장하는 array
(one's count of ith~jth substring) = P[j] - P[i]
(zero's count of ith~jth substring) = (j-i+1) - (P[j] - P[i])

우리가 구하고자 하는 건 monotone string을 만들 때 0 또는 1을 최소한으로 바꾸는 수이다. 이를 구하기 위해선 0번째 index에서 시작해 n번째 index까지 monotone string을 만들기 위한 개수를 구하고, 이들 값 중 최소값을 return하면 된다. 기준점이 되는 i번째 index가 있을텐데, 그 값을 정확히 모르므로 전체 array를 재탐색한다. pseudo-code는 다음과 같다.

P → 1의 개수를 저장하는 array
n → string의 길이
ans → 결과값
for (0 <= i <=n)
    ans = min(ans, P[i] + (n-i) - (P[n] - P[i]))

위에서 P[i]가 0에서 i까지 substing에서 0으로 바꿔야 할 1의 개수, (n-i) - (P[n] - P[i])가 i+1에서 n-1까지 substring에서 1으로 바꿔야 할 0의 개수를 나타낸다.

Solution

class Solution {
    public int minFlipsMonoIncr(String s) {
    	int n = s.length();
        int[] runningOneCnt = new int[n+1];

	for (int i=0; i < n; i++)
            runningOneCnt[i+1] = runningOneCnt[i] + (s.charAt(i) == '1' ? 1 : 0);

    	int ans = Integer.MAX_VALUE;
    	for (int i=0; i <= n; i++) {
            ans = Math.min(ans, runningOneCnt[i] + (n-i) - (runningOneCnt[n] - runningOneCnt[i]));
    	}

    	return ans;
    }
}

Reference

https://leetcode.com/problems/flip-string-to-monotone-increasing/