#2381

Medium

LeetCode Problem Workspace

Shifting Letters II

Shift letters in a string using a sequence of range-based forward or backward operations efficiently with prefix sums.

Problem Statement

Given a lowercase string s and a 2D integer array shifts where shifts[i] = [start, end, direction], apply the shifts in order: for each i, move letters from start to end forward if direction is 1, or backward if direction is 0. Each forward shift moves a letter to the next alphabet character wrapping 'z' to 'a'; each backward shift moves to the previous letter wrapping 'a' to 'z'.

Return the final string after performing all the shifts. For example, with s = "abc" and shifts = [[0,1,0],[1,2,1],[0,2,1]], the output is "ace" because applying the shifts sequentially transforms the string accordingly.

Examples

Example 1

Input: s = "abc", shifts = [[0,1,0],[1,2,1],[0,2,1]]

Output: "ace"

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"

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 Approach

Use a difference array for efficient range shifts

Instead of updating each character per shift, create a difference array to track net shifts for each position. Increment the start index by +1 or -1 based on direction and decrement the index after the end.

Compute cumulative shifts

Convert the difference array into a prefix sum array to determine the total shift for each character. This step aggregates all shifts affecting each position efficiently in a single pass.

Apply the shifts to the string

For each character in the string, apply the cumulative shift modulo 26 to handle wrap-around. Construct the final string by shifting each character according to its net calculated shift.

Complexity Analysis

Metric	Value
Time	O(n + m)
Space	O(n)

Time complexity is O(n + m) where n is the string length and m is the number of shifts, as we process shifts in a difference array and apply cumulative shifts once. Space complexity is O(n) for the difference array storing net shifts.

What Interviewers Usually Probe

Can you avoid applying each shift individually?
What if the shifts array is very large and direct updates are too slow?
How can prefix sums optimize cumulative letter transformations?

Common Pitfalls or Variants

Common pitfalls

Forgetting to wrap around 'z' to 'a' or 'a' to 'z'.
Incorrectly applying backward shifts as negative increments without proper modulo handling.
Updating characters per shift instead of using a prefix sum leads to timeouts on large inputs.

Follow-up variants

Shifting letters with non-overlapping ranges only.
Shifting letters with variable shift amounts instead of single-step forward/backward.
Applying shifts on strings with uppercase letters, requiring separate ASCII handling.

FAQ

What is the main pattern in Shifting Letters II?

It combines array range updates with string character shifts, solved efficiently using difference arrays and prefix sums.

How do you handle backward shifts in this problem?

Treat backward shifts as negative increments in the difference array and apply modulo 26 when computing final letters.

Can I apply each shift directly on the string?

Direct updates per shift are inefficient for large inputs and may cause timeouts; using a prefix sum array is faster.

How do wrap-around shifts work in Shifting Letters II?

Forward shifts wrap 'z' to 'a' and backward shifts wrap 'a' to 'z', which is handled using modulo 26 arithmetic.

What is the time complexity of the optimal solution?

O(n + m), where n is the length of the string and m is the number of shifts, because each character is shifted once after computing cumulative sums.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:
        n = len(s)
        d = [0] * (n + 1)
        for i, j, v in shifts:
            if v == 0:
                v = -1
            d[i] += v
            d[j + 1] -= v
        for i in range(1, n + 1):
            d[i] += d[i - 1]
        return ''.join(
            chr(ord('a') + (ord(s[i]) - ord('a') + d[i] + 26) % 26) for i in range(n)
        )

Continue Practicing

#2391 minimum amount of time to collect garbage #2559 count vowel strings in ranges #2055 plates between candles