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.

Approach 01:

#include <vector>
#include <string>
using namespace std;

class Solution {
public:
    string shiftingLetters(string s, vector<vector<int>>& shifts) {
        int accumulatedShift = 0;  // Accumulated shift at each position
        vector<int> shiftDifferences(s.length() + 1, 0);  // Timeline of shifts

        // Apply shifts to the timeline
        for (const vector<int>& shift : shifts) {
            const int startIdx = shift[0];  // Starting index for the shift
            const int endIdx = shift[1];    // Ending index for the shift
            const int direction = shift[2];  // Direction of the shift (1 for right, 0 for left)
            const int shiftValue = direction ? 1 : -1;  // +1 for right shift, -1 for left shift
            shiftDifferences[startIdx] += shiftValue;
            shiftDifferences[endIdx + 1] -= shiftValue;
        }

        // Apply the accumulated shifts to the string
        for (int i = 0; i < s.length(); ++i) {
            accumulatedShift = (accumulatedShift + shiftDifferences[i]) % 26;
            const int newCharPos = (s[i] - 'a' + accumulatedShift + 26) % 26;
            s[i] = 'a' + newCharPos;
        }

        return s;
    }
};

class Solution:
    def shiftingLetters(self, s: str, shifts: list[list[int]]) -> str:
        accumulatedShift = 0  # Accumulated shift at each position
        shiftDifferences = [0] * (len(s) + 1)  # Timeline of shifts

        # Apply shifts to the timeline
        for shift in shifts:
            startIdx = shift[0]  # Starting index for the shift
            endIdx = shift[1]    # Ending index for the shift
            direction = shift[2]  # Direction of the shift (1 for right, 0 for left)
            shiftValue = 1 if direction else -1  # +1 for right shift, -1 for left shift
            shiftDifferences[startIdx] += shiftValue
            shiftDifferences[endIdx + 1] -= shiftValue

        # Apply the accumulated shifts to the string
        s = list(s)  # Convert string to list for mutable operations
        for i in range(len(s)):
            accumulatedShift = (accumulatedShift + shiftDifferences[i]) % 26
            newCharPos = (ord(s[i]) - ord('a') + accumulatedShift + 26) % 26
            s[i] = chr(ord('a') + newCharPos)

        return ''.join(s)

Time Complexity:

• Applying Shifts to the Timeline:

  Each shift is processed once, resulting in \( O(m) \), where \( m \) is the number of shift operations.

• Applying Accumulated Shifts to the String:

  Iterating over the string takes \( O(n) \), where \( n \) is the length of the string.

• Overall Time Complexity:

  \( O(n + m) \), as the contributions of both steps are additive.

Space Complexity:

• Shift Differences Array:

  An auxiliary array of size \( n + 1 \) is used, contributing \( O(n) \).

• Other Variables:

  Constant space is used for variables like accumulatedShift and newCharPos, contributing \( O(1) \).

• Overall Space Complexity:

  \( O(n) \), as the array dominates the space usage.