▲

3

▼

🚀 Минимальное число перекрашиваний: метод скользящего окна 🚀

leetcoder, 08-03-2025 , 307

Ссылка на задачу — 2379. Minimum Recolors to Get K Consecutive Black Blocks.

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

Дана строка blocks, состоящая из символов 'W' (белый) и 'B' (чёрный).
Необходимо определить минимальное число перекрашиваний белых блоков в чёрные, чтобы получить хотя бы одну последовательность из k подряд идущих чёрных блоков.

💡 Идея

Используем технику скользящего окна:

• будем двигать окно размера k по строке и считать количество белых блоков внутри окна;
• минимальное количество белых блоков среди всех окон и будет ответом.

📖 Детали подхода

1. Посчитаем число белых блоков в первом окне размера k.
2. Сдвигаем окно вправо на один символ за раз:
   • если символ, который «входит» в окно, белый ('W'), увеличиваем счётчик;
   • если символ, который «выходит» из окна, белый, уменьшаем счётчик.
3. После каждого сдвига окна обновляем минимальное найденное значение.
4. Итоговый ответ — это минимальное число белых блоков за всё время обхода.

⏳ Асимптотика

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

🛠️ Исходный код

impl Solution {
    pub fn minimum_recolors(blocks: String, k: i32) -> i32 {
        let blocks = blocks.as_bytes();
        let k = k as usize;

        // Count white blocks ('W') in the first window of size k
        let initial_recolors = blocks[..k].iter().filter(|&&b| b == b'W').count() as i32;

        // Slide window over the blocks using iterator methods
        blocks
            .windows(k+1)
            .fold((initial_recolors, initial_recolors), |(current, min), window| {
                // Update recolors based on outgoing and incoming blocks
                let next = current 
                    + (window.last() == Some(&b'W')) as i32 
                    - (window.first() == Some(&b'W')) as i32;

                (next, min.min(next))
            }).1
    }
}

Tags: #rust #algorithms #counting