▲

3

▼

🚀 Оптимальное применение сдвига символов строки с использованием префиксных сумм

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

Задача на сегодня 2381. Shifting Letters II - решается несложно, но используемая идея мне лично кажется интересной и симпатичной.

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

Дана строка s и список операций shifts, где каждая операция задаёт начало и конец диапазона, а также направление (вперёд или назад).
Ваша задача — применить все сдвиги к строке и вернуть окончательный результат.

Идея 🔄

Для оптимизации решения и избежания повторных расчётов сдвигов, мы используем алгоритм, основанный на префиксных суммах. Это позволяет эффективно сохранять кумулятивный эффект от всех сдвигов в отдельном массиве и применять их конечному результату за один проход.

Детали решения 📝

1. Создадим массив net_shifts, где будут храниться чистые значения сдвигов для каждой позиции в строке.
2. Пройдемся по всем операциям и обновим массив net_shifts, добавляя значения в начале диапазона и вычитая их сразу после его окончания.
3. Произведем один последовательный проход по строке, вычисляя кумулятивные сдвиги и применяя их для каждого символа.

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

• Время: O(n + m), где n — длина строки, m — количество операций.
• Память: O(n) для массива net_shifts.

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

impl Solution {
    pub fn shifting_letters(s: String, shifts: Vec<Vec<i32>>) -> String {
        // Track the net shift values for each character in the string
        let mut net_shifts = vec![0; s.len()];
        for shift in shifts {
            let (start, end, direction) = (shift[0] as usize, shift[1] as usize, shift[2]);
            let shift_value = if direction == 1 { 1 } else { -1 };

            net_shifts[start] += shift_value;
            if end + 1 < s.len() {
                net_shifts[end + 1] -= shift_value;
            }
        }

        // Apply cumulative shifts and build the resulting string
        let mut cumulative_shift = 0;
        s.bytes()
            .enumerate()
            .map(|(i, byte)| {
                cumulative_shift = (cumulative_shift + net_shifts[i] + 26) % 26;
                let char_index = ((byte - b'a') as i32 + cumulative_shift) % 26;
                (b'a' + char_index as u8) as char
            })
            .collect()
    }
}