926. Flip String to Monotone Increasing

leetcode medium

#array#csharp#leetcode#math#medium#string#two-pointers

Task

Двоичная строка является монотонно возрастающей, если она состоит из некоторого количества 0 (возможно, ни одного), за которым следует некоторое количество 1 (также возможно, ни одного). Вам дана двоичная строка s. Вы можете перевернуть s[i], изменив ее значение с 0 на 1 или с 1 на 0.

Пример:

Input: s = "00110"

Output: 1

C# solution

matched/original

public class Solution {
    public int MinFlipsMonoIncr(string s) {
        int n = s.Length;
        int[] left = new int[n + 1];
        int[] right = new int[n + 1];
        
        for (int i = 0; i < n; i++) {
            left[i + 1] = left[i] + (s[i] == '1' ? 1 : 0);
        }
        
        for (int i = n - 1; i >= 0; i--) {
            right[i] = right[i + 1] + (s[i] == '0' ? 1 : 0);
        }
        
        int result = int.MaxValue;
        for (int i = 0; i <= n; i++) {
            result = Math.Min(result, left[i] + right[i]);
        }
        return result;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int MinFlipsMonoIncr(string s) {
        int n = s.size();
        vector<int>& left = new int[n + 1];
        vector<int>& right = new int[n + 1];
        
        for (int i = 0; i < n; i++) {
            left[i + 1] = left[i] + (s[i] == '1' ? 1 : 0);
        }
        
        for (int i = n - 1; i >= 0; i--) {
            right[i] = right[i + 1] + (s[i] == '0' ? 1 : 0);
        }
        
        int result = int.MaxValue;
        for (int i = 0; i <= n; i++) {
            result = min(result, left[i] + right[i]);
        }
        return result;
    }
}

Java solution

matched/original

class Solution {
    public int minFlipsMonoIncr(String s) {
        int n = s.length();
        int[] left = new int[n + 1];
        int[] right = new int[n + 1];
        
        for (int i = 0; i < n; i++) {
            left[i + 1] = left[i] + (s.charAt(i) == '1' ? 1 : 0);
        }
        
        for (int i = n - 1; i >= 0; i--) {
            right[i] = right[i + 1] + (s.charAt(i) == '0' ? 1 : 0);
        }
        
        int result = Integer.MAX_VALUE;
        for (int i = 0; i <= n; i++) {
            result = Math.min(result, left[i] + right[i]);
        }
        return result;
    }
}

Explanation

Algorithm

Создать массив left для подсчета количества операций, чтобы сделать подстроку до текущего индекса монотонной (только 0).

Создать массив right для подсчета количества операций, чтобы сделать подстроку после текущего индекса монотонной (только 1).

Пройти по строке и заполнить массивы left и right.

Пройти по строке и найти минимальное количество операций, чтобы сделать всю строку монотонной.

😎