Задача: 926. Flip String to Monotone Increasing
Сложность: medium

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

Пример:

Input: s = "00110"
Output: 1

👨‍💻 Алгоритм:

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

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

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

😎 Решение:

class Solution {
    func minFlipsMonoIncr(_ s: String) -> Int {
        let n = s.count
        var left = [Int](repeating: 0, count: n + 1)
        var right = [Int](repeating: 0, count: n + 1)
        let sArray = Array(s)
        
        for i in 0..<n {
            left[i + 1] = left[i] + (sArray[i] == "1" ? 1 : 0)
        }
        
        for i in (0..<n).reversed() {
            right[i] = right[i + 1] + (sArray[i] == "0" ? 1 : 0)
        }
        
        var result = Int.max
        for i in 0...n {
            result = min(result, left[i] + right[i])
        }
        return result
    }
}

Ставь 👍 и забирай 📚 Базу знаний