🚀 Оптимизация разбиения бинарной строки за один проход

leetcoder, изменено 13-01-2025 ,

277

Первая задача в этом году - 1422. Maximum Score After Splitting a String несложная, и интересно решить её за один проход по массиву.

📋 Описание задачи

Дана бинарная строка, состоящая из символов 0 и 1.
Требуется найти максимальный результат разбиения строки на две непустые подстроки.
Результат определяется как:

Результат = (Количество нулей в левой подстроке) + (Количество единиц в правой подстроке).

💡 Идея

Для эффективного решения задачи:

Рассчитаем динамический баланс для каждого допустимого разбиения строки. Баланс показывает, насколько выгодно разделить строку в конкретной точке.
Пройдем по строке, обновляя текущий баланс и максимальный результат. Пропустим последнюю итерацию, чтобы обе подстроки оставались непустыми.

🔍 Подробности подхода

Формула результата: Для разбиения в точке i:
- Result = zero_count + (total_ones - ones_count)
  , где:
  - zero_count – число нулей слева
  - ones_count – число единиц слева (ones_count = i+1 - zero_count)
  - total_ones – число единиц во всей строке
Упрощение формулы: Подставляем значение для ones_count
- Result = 2 · zero_count - i - 1 + total_ones
- Постоянную часть total_ones - 1 можно игнорировать и максимизировать:
- balance = 2 · zero_count - i
Итеративный процесс:
- Увеличиваем zero_count, если встречаем 0.
- Пропускаем последнюю итерацию, чтобы обе подстроки были непустыми.
- Рассчитываем и обновляем max_balance.
Финальная формула: После прохода по строке итоговый результат рассчитывается как:
- Result = (str_length - zero_count) + max_balance-1

⏱️ Асимптотика

Время: O(n) — однократный проход по строке.
Память: O(1) — используются только переменные zero_count и max_balance.

💻 Исходный код

impl Solution {
    pub fn max_score(s: String) -> i32 {
        let n = s.len();
        let mut zero_count = 0; // Number of zeros in the left part
        let mut max_balance = i32::MIN;

        // Iterate over the string
        for (i, c) in s.chars().enumerate() {
            if c == '0' {
                zero_count += 1; // Increase zeros number
            }

            // Pass the last iteration, because both substrings should be non empty
            if i + 1 < n {
                let balance = 2 * zero_count as i32 - i as i32;
                max_balance = max_balance.max(balance); // Update maximal balance
            }
        }

        // Final result calculations
        (n - 1) as i32 + max_balance - zero_count as i32
    }
}