README.md

2381. Shifting Letters II

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.

Example 1:

Input: s = "abc", shifts = [[0,1,0],[1,2,1],[0,2,1]]
Output: "ace"
Explanation: Firstly, shift the characters from index 0 to index 1 backward. Now s = "zac".
Secondly, shift the characters from index 1 to index 2 forward. Now s = "zbd".
Finally, shift the characters from index 0 to index 2 forward. Now s = "ace".

Example 2:

Input: s = "dztz", shifts = [[0,0,0],[1,1,1]]
Output: "catz"
Explanation: Firstly, shift the characters from index 0 to index 0 backward. Now s = "cztz".
Finally, shift the characters from index 1 to index 1 forward. Now s = "catz".

Constraints:

• 1 <= s.length, shifts.length <= 5 * 104
• shifts[i].length == 3
• 0 <= starti <= endi < s.length
• 0 <= directioni <= 1
• s consists of lowercase English letters.

Solutions (Rust)

1. Solution

impl Solution {
    pub fn shifting_letters(s: String, shifts: Vec<Vec<i32>>) -> String {
        let mut s = s.into_bytes();
        let mut prefix_sum = vec![0; s.len()];

        for i in 0..shifts.len() {
            if shifts[i][0] > 0 {
                prefix_sum[shifts[i][0] as usize - 1] -= 2 * shifts[i][2] - 1;
            }
            prefix_sum[shifts[i][1] as usize] += 2 * shifts[i][2] - 1;
        }

        for i in (0..prefix_sum.len()).rev() {
            prefix_sum[i] += *prefix_sum.get(i + 1).unwrap_or(&0);
            s[i] = ((s[i] - b'a') as i32 + prefix_sum[i]).rem_euclid(26) as u8 + b'a';
        }

        String::from_utf8(s).unwrap()
    }
}