Problem

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.

Examples

Example 1:

1
2
3
4
5

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:

1
2
3
4

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.

Solution

Method 1 - Diffs with Prefix Sum

Here is the approach:

  1. Initialisation of the Difference Array:
    • Create a difference array diff of the same length as the string s and initialise it with zeroes.
    • For each shift operation, update the start and end indices of the diff array based on the direction (forward or backward shift).
  2. Applying the Shifts:
    • Traverse through the shifts array.
    • If directioni == 1, increase diff[starti] by 1 and decrease diff[endi + 1] by 1.
    • If directioni == 0, decrease diff[starti] by 1 and increase diff[endi + 1] by 1.
  3. Creating the Final Shift Pattern:
    • Convert the diff array into a cumulative sum array to get the net shift at each character index.
  4. *Applying the Shifts to the String:
    • Traverse through the string s and apply the calculated shifts. Wrap around using modulo operation for alphabetic shifts.
  5. Finalize the Result:
    • Construct the final string from the updated characters.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class Solution {
    public String shiftingLetters(String s, int[][] shifts) {
        int n = s.length();
        int[] diff = new int[n + 1];

        for (int[] shift : shifts) {
            int start = shift[0], end = shift[1], dir = shift[2];
            if (dir == 1) {
                diff[start]++;
                if (end + 1 < n) diff[end + 1]--;
            } else {
                diff[start]--;
                if (end + 1 < n) diff[end + 1]++;
            }
        }

        int netShift = 0;
        char[] ans = s.toCharArray();
        for (int i = 0; i < n; i++) {
            netShift += diff[i];
            int shift = ((netShift % 26) + 26) % 26;
            ans[i] = (char) ((ans[i] - 'a' + shift) % 26 + 'a');
        }

        return new String(ans);
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution:
    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:
        n: int = len(s)
        diff: List[int] = [0] * (n + 1)

        for start, end, direction in shifts:
            if direction == 1:
                diff[start] += 1
                if end + 1 < n:
                    diff[end + 1] -= 1
            else:
                diff[start] -= 1
                if end + 1 < n:
                    diff[end + 1] += 1

        net_shift: int = 0
        ans: List[str] = list(s)
        for i in range(n):
            net_shift += diff[i]
            shift = (net_shift % 26 + 26) % 26
            ans[i] = chr((ord(ans[i]) - ord('a') + shift) % 26 + ord('a'))

        return ''.join(ans)

Complexity

  • ⏰ Time complexity: O(n + m) where n is the length of the string s and m is the number of shifts.
  • 🧺 Space complexity: O(n), mainly for the difference array.