Shifting letters ii

Array String Prefix Sum

53.5% acceptance

Feb 25, 2026

1761

You are given a string s of lowercase English letters and a 2D integer array shifts where shifts[i] = [starti, endi, directioni]. For every i, shift the characters in s from the index starti to the index endi (inclusive) forward if directioni = 1, or shift the characters backward if directioni = 0. Shifting a character forward means replacing it with the next letter in the alphabet (wrapping around so that 'z' becomes 'a'). Similarly, shifting a character backward means replacing it with the previous letter in the alphabet (wrapping around so that 'a' becomes 'z'). Return the final string after all such shifts to s are applied.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn shifting_letters(s: String, shifts: Vec<Vec<i32>>) -> String {
    let n = s.len();
    let mut diff = vec![0i64; n + 1];
    for sh in &shifts {
      let (start, end, dir) = (sh[0] as usize, sh[1] as usize, sh[2]);
      let delta = if dir == 1 { 1i64 } else { -1 };
      diff[start] += delta;
      diff[end + 1] -= delta;
    }
    let mut bytes: Vec<u8> = s.bytes().collect();
    let mut shift = 0i64;
    for i in 0..n {
      shift += diff[i];
      let c = (bytes[i] - b'a') as i64;
      bytes[i] = b'a' + (c + shift).rem_euclid(26) as u8;
    }
    String::from_utf8(bytes).unwrap()
  }
}