LeetCode Entry

2381. Shifting Letters II

05.01.2025 medium 2025 kotlin rust

Apply from..to, direction shifts to string chars sweep

2381. Shifting Letters II medium blog post substack youtube deep-dive

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/855

Problem TLDR

Apply from..to, direction shifts to string chars #medium #line_sweep

Intuition

We can sort the shifts intervals, then walk them, calculating the running value of shift.

One optimization is to store the starts and ends of each shift in a cumulative shifts array, then scan it’s running value in a linear way.

Approach

• in Rust we can modify the stirng in-place with unsafe { s.as_bytes_mut() }
• the difference betwen auto s: shifts and auto &s: shifts in c++ is 4ms vs 40ms

Complexity

• Time complexity: \(O(n)\)

• Space complexity: \(O(n)\)

Code

    fun shiftingLetters(s: String, shifts: Array<IntArray>) = buildString {
        val shift = IntArray(s.length + 1); var sh = 0
        for ((s, e, d) in shifts) {
            shift[s] += d * 2 - 1
            shift[e + 1] -= d * 2 - 1
        }
        for ((i, c) in s.withIndex()) {
            sh += shift[i]
            append('a' + (c - 'a' + sh % 26 + 26) % 26)
        }
    }

    pub fn shifting_letters(s: String, shifts: Vec<Vec<i32>>) -> String {
        let (mut shift, mut sh, mut r) = (vec![0; s.len() + 1], 0, vec![0; s.len()]);
        for sh in shifts {
            let (s, e, d) = (sh[0] as usize, sh[1] as usize, sh[2] * 2 - 1);
            shift[s] += d; shift[e + 1] -= d
        }
        for (i, c) in s.bytes().enumerate() {
            sh += shift[i];
            r[i] = b'a' + (c - b'a' + (sh % 26 + 26) as u8) % 26
        }; String::from_utf8(r).unwrap()
    }

    string shiftingLetters(string s, vector<vector<int>>& shifts) {
        int sh[50001] = {0}, d = 0;
        for (auto &s: shifts)
            sh[s[0]] += s[2] * 2 - 1, sh[s[1] + 1] -= s[2] * 2 - 1;
        for (int i = 0; i < s.size(); ++i)
            s[i] = 'a' + (s[i] - 'a' + (d += sh[i]) % 26 + 26) % 26;
        return s;
    }