Shifting Letters II LeetCode 2381 Guide

LeetCode 2381 Shifting Letters II gives you a string s of lowercase English letters and an array shifts where each element is [start, end, direction]. The direction value 1 means shift forward (a→b, b→c, …, z→a) and 0 means shift backward (b→a, a→z, …). All shifts are applied simultaneously to produce the final result string.

The challenge is that multiple shifts can overlap the same index. A character at position i accumulates the net effect of every shift whose range covers i. If the net shift is positive, the character moves forward that many steps in the alphabet; if negative, it moves backward. Both directions wrap around: shifting z forward gives a, and shifting a backward gives z.

A brute-force approach — iterating over every character in every shift range — is O(n × q) where n is the string length and q is the number of shifts. With constraints up to n = 5 × 10^4 and q = 5 × 10^4, this is 2.5 billion operations in the worst case and will time out. The efficient solution uses a difference array to reduce each range update to O(1), then a single O(n) prefix sum pass.

The difference array is a classic technique for batch range-update problems. Instead of incrementing every element in a range [l, r] by some value v — which takes O(n) per update — you record just two boundary markers: add v at index l and subtract v at index r+1. This makes each update O(1).

After all updates are recorded, a single left-to-right prefix sum pass reconstructs the cumulative value at every index. The prefix sum at index i equals the sum of all v values for ranges that started at or before i and have not yet ended (i.e., their r+1 marker has not been reached). This gives the exact net shift for each character position in one O(n) pass.

For this problem, a forward shift (direction 1) contributes +1 to the net shift over its range, and a backward shift (direction 0) contributes -1. After the prefix sum, the net shift at each position tells you exactly how many steps forward (positive) or backward (negative) to shift the character, modulo 26.

Create a difference array diff of size n+1, initialized to all zeros. The extra element at index n acts as a sentinel — it absorbs the closing -1 markers for ranges ending at index n-1 without going out of bounds. Iterate through every shift [l, r, d]: if d is 1 (forward), add 1 at diff[l] and subtract 1 at diff[r+1]; if d is 0 (backward), subtract 1 at diff[l] and add 1 at diff[r+1].

After processing all shifts, compute the prefix sum of diff in place. After this pass, diff[i] holds the net shift that must be applied to character s[i]. The prefix sum accumulates all the boundary markers into a running total, effectively "spreading" each range update across its full extent.

Finally, iterate through each position i of s. Compute newChar = (s[i] - 'a' + diff[i] % 26 + 26) % 26 + 'a'. The % 26 reduces the net shift to a value in the range (-25, 25). The + 26 ensures the result is non-negative before the final % 26, handling backward shifts that would otherwise produce a negative modulo. Append each new character to the result.

Once the prefix sum gives the net shift at each position, converting a character is straightforward. Treat the character as an offset from 'a': the offset of 'a' is 0, 'b' is 1, …, 'z' is 25. Add the net shift to this offset, take mod 26 to wrap around the alphabet, then convert back to a character by adding the ASCII value of 'a'.

The net shift may be large in magnitude — if many shifts overlap a single position, the accumulated value could be far outside [0, 25]. Taking netShift % 26 first reduces it to a small value, but the result may still be negative if the net direction was backward. Adding 26 before the final % 26 corrects this: (netShift % 26 + 26) % 26 always produces a value in [0, 25].

In Python, the expression (ord(s[i]) - ord('a') + netShift % 26 + 26) % 26 + ord('a') produces the correct ASCII code of the shifted character. In Java, casting and integer arithmetic are equivalent: (s.charAt(i) - 'a' + netShift % 26 + 26) % 26 + 'a'. Build the result as a char array in Java for efficiency, or use a list joined at the end in Python.

Consider s = "abc" and shifts = [[0,1,0],[1,2,1],[0,2,1]]. The string has length 3, so diff has size 4, initialized to [0,0,0,0]. Process shift [0,1,0] (backward, d=0): diff[0] -= 1 → -1; diff[2] += 1 → 1. diff is now [-1,0,1,0]. Process shift [1,2,1] (forward, d=1): diff[1] += 1 → 1; diff[3] -= 1 → -1. diff is now [-1,1,1,-1]. Process shift [0,2,1] (forward, d=1): diff[0] += 1 → 0; diff[3] -= 1 → -2. diff is now [0,1,1,-2].

Now compute the prefix sum: diff[0] stays 0; diff[1] = 0+1 = 1; diff[2] = 1+1 = 2; diff[3] = 2+(-2) = 0 (sentinel, unused). The net shifts are [0, 1, 2] for positions 0, 1, 2 respectively. Apply: position 0 — 'a' + 0 = 'a'; position 1 — 'b' + 1 = 'c'; position 2 — 'c' + 2 = 'e'. Result is "ace".

Let's verify manually. Shift [0,1,0] shifts s[0] and s[1] backward by 1: a→z, b→a. Shift [1,2,1] shifts s[1] and s[2] forward: b→c, c→d. Shift [0,2,1] shifts all forward: a→b, b→c, c→d. At s[0]: start 'a', backward 1 (→z), forward 1 (→a). Net = 0 → 'a'. At s[1]: start 'b', backward 1 (→a), forward 1 (→b), forward 1 (→c). Net = +1 → 'c'. At s[2]: start 'c', forward 1 (→d), forward 1 (→e). Net = +2 → 'e'. Result: "ace". Confirmed.

Python solution: def shiftingLetters(s, shifts): n = len(s); diff = [0] * (n + 1); for l, r, d in shifts: v = 1 if d == 1 else -1; diff[l] += v; diff[r+1] -= v; for i in range(1, n): diff[i] += diff[i-1]; return ''.join(chr((ord(c) - ord('a') + diff[i] % 26 + 26) % 26 + ord('a')) for i, c in enumerate(s)). Time O(n + q), space O(n) for the diff array.

Java solution: public String shiftingLetters(String s, int[][] shifts) { int n = s.length(); int[] diff = new int[n + 1]; for (int[] sh : shifts) { int v = sh[2] == 1 ? 1 : -1; diff[sh[0]] += v; diff[sh[1]+1] -= v; } for (int i = 1; i < n; i++) diff[i] += diff[i-1]; char[] res = s.toCharArray(); for (int i = 0; i < n; i++) { int shift = ((diff[i] % 26) + 26) % 26; res[i] = (char)((res[i] - 'a' + shift) % 26 + 'a'); } return new String(res); }

Both solutions run in O(n + q) time: O(q) to fill the diff array, O(n) for the prefix sum, O(n) to build the result. Space is O(n) for the diff array and O(n) for the output. The diff array needs size n+1 to safely write diff[r+1] when r = n-1 without an out-of-bounds error. The prefix sum is computed only up to index n-1; the sentinel at index n is never used in the character application step.

Range Sum Query — Immutable (LeetCode 303) is the foundational prefix sum problem: precompute cumulative sums so that any range sum query is answered in O(1). The difference array is the inverse concept — instead of querying cumulative sums, you accumulate update boundaries and compute the final values in one pass. Understanding both directions (prefix sum for queries, difference array for updates) is essential for interval and range problems.

Find Pivot Index (LeetCode 724) asks for the index where the left sum equals the right sum, which is solved with a prefix sum scan. It reinforces the left-to-right accumulation pattern used in the difference array prefix sum step. Problems in the range-update family include Car Pooling (LeetCode 1094), Corporate Flight Bookings (LeetCode 1109), and Number of Flowers in Full Bloom (LeetCode 2251), all of which use the same mark-boundaries-then-prefix-sum strategy.

The broader array algorithms family includes sliding window techniques, two-pointer methods, and monotonic stack/queue patterns. The difference array fits within the "transform the problem to avoid redundant work" theme — instead of repeatedly scanning ranges, you encode the range structure once and decode it efficiently. Recognizing when a problem asks for simultaneous range updates on an array is the key trigger for reaching for the difference array technique.