Shifting Letters II — Difference Array vs Segment Tree Range Update Patterns

Problem Statement#

LeetCode 2381 — Shifting Letters II | Difficulty: Medium

You are given a string s of lowercase English letters and a 2D array shifts where shifts[i] = [start_i, end_i, direction_i].

For every shift, do the following on the substring s[start_i .. end_i] inclusive:

• If direction_i is 1, shift each letter forward by 1 (z wraps to a).
• If direction_i is 0, shift each letter backward by 1 (a wraps to z).

Return the final string after all shifts.

Constraints:

• 1 is less than or equal to s.length, which is less than or equal to 5 * 10^4
• 1 is less than or equal to shifts.length, which is less than or equal to 5 * 10^4
• 0 is less than or equal to start_i, which is less than or equal to end_i, which is less than s.length
• 0 is less than or equal to direction_i, which is less than or equal to 1

Example:

Input:  s = "abc", shifts = [[0, 1, 0], [1, 2, 1], [0, 2, 1]]
Output: "ace"
Explanation:
  shift [0,1] by -1:  "abc" -> "zac"  (a -> z, b -> a, c stays)
  shift [1,2] by +1:  "zac" -> "zbd"  (a -> b, c -> d)
  shift [0,2] by +1:  "zbd" -> "ace"  (z -> a, b -> c, d -> e)

Why This Problem Matters#

Shifting Letters II is the textbook interview problem for the difference-array trick. Google, Amazon, and Meta use it to test whether you instinctively reach for the cheapest data structure that fits the operation profile — in this case all updates first, then a single read pass at the end, also known as the offline range-update plus point-query workload.

Many candidates over-engineer this with a segment tree and lazy propagation. That works but it is wasteful: when you do not need any intermediate queries, a difference array gives O(n + q) with one prefix-sum pass — strictly better than O((n + q) log n). Recognizing this trade-off is the senior signal interviewers grade for.

The Core Insight#

A difference array diff[] lets you apply a range update [L, R] of magnitude v in O(1):

• diff[L] += v
• diff[R + 1] -= v

After all updates, the prefix sum of diff gives the net value at each position. Total cost: O(q) for q updates plus O(n) for the prefix sum pass = O(n + q).

For this problem, encode each shift as plus 1 (forward) or minus 1 (backward), accumulate all shifts via the difference array, then sweep left to right computing the running shift. Apply the running shift mod 26 to each character.

Why not a segment tree with lazy propagation?

• A segment tree would handle this too, but at O(q log n) for updates.
• The trade-off is decisive when there are no intermediate queries: every interim state is wasted work.
• Use a segment tree only when you need queries interleaved with updates.

Why not iterate each shift directly?

• Worst case is q * n = 2.5 * 10^9 operations on the upper constraint. That times out.
• The diff trick batches all updates into O(q) constant-time stamps and a single O(n) sweep.

Visual Dry Run#

Trace s = "abc", shifts = [[0,1,0], [1,2,1], [0,2,1]].

Initialize diff = [0, 0, 0, 0]   (size n+1 = 4)
 
Apply [0, 1, 0]: backward, v = -1
  diff[0] += -1 -> diff = [-1, 0, 0, 0]
  diff[2] -= -1 -> diff = [-1, 0, 1, 0]
 
Apply [1, 2, 1]: forward, v = +1
  diff[1] += 1 -> diff = [-1, 1, 1, 0]
  diff[3] -= 1 -> diff = [-1, 1, 1, -1]
 
Apply [0, 2, 1]: forward, v = +1
  diff[0] += 1 -> diff = [0, 1, 1, -1]
  diff[3] -= 1 -> diff = [0, 1, 1, -2]
 
Prefix sweep (running shift):
  i=0: shift = 0,        applied to 'a' -> 'a'
  i=1: shift = 0+1 = 1,  applied to 'b' -> 'c'
  i=2: shift = 1+1 = 2,  applied to 'c' -> 'e'
 
Result: "ace"

The four diff updates plus three sweep steps produce the answer. No segment tree needed.

Solution (Optimal)#

Python — Difference Array#

from typing import List
 
class Solution:
    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:
        n = len(s)
        diff = [0] * (n + 1)                            # n+1 to safely write at end+1
 
        # apply all range updates in O(1) each
        for L, R, d in shifts:
            v = 1 if d == 1 else -1                     # forward = +1, backward = -1
            diff[L] += v
            diff[R + 1] -= v
 
        # single prefix-sum sweep produces final string
        result = []
        running = 0
        for i, ch in enumerate(s):
            running += diff[i]                          # accumulate net shift at i
            shifted = (ord(ch) - ord('a') + running) % 26  # mod 26 handles wrap-around
            result.append(chr(shifted + ord('a')))
        return ''.join(result)

JavaScript — Difference Array#

var shiftingLetters = function(s, shifts) {
    const n = s.length;
    const diff = new Array(n + 1).fill(0);             // sentinel slot at n
 
    // record each shift as a range delta
    for (const [L, R, d] of shifts) {
        const v = d === 1 ? 1 : -1;                    // direction encoding
        diff[L] += v;                                   // start of range
        diff[R + 1] -= v;                               // one past end
    }
 
    // prefix sum gives net shift at each position; build result string
    let running = 0;
    const out = [];
    for (let i = 0; i < n; i++) {
        running += diff[i];                             // net shift at i
        // ((shift % 26) + 26) % 26 handles negative modulo correctly
        const code = ((s.charCodeAt(i) - 97 + running) % 26 + 26) % 26;
        out.push(String.fromCharCode(code + 97));
    }
    return out.join('');
};

Python — Segment Tree with Lazy Propagation (For Comparison)#

# Useful only if intermediate queries are needed; otherwise the diff array dominates.
from typing import List
 
class Solution:
    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:
        n = len(s)
        tree = [0] * (4 * n)
        lazy = [0] * (4 * n)
 
        def push_down(node, l, r):
            if lazy[node]:
                mid = (l + r) // 2
                # push lazy add to children
                tree[2 * node] += lazy[node]
                lazy[2 * node] += lazy[node]
                tree[2 * node + 1] += lazy[node]
                lazy[2 * node + 1] += lazy[node]
                lazy[node] = 0
 
        def update(node, l, r, ql, qr, val):
            if qr < l or r < ql: return
            if ql <= l and r <= qr:
                tree[node] += val                       # range add
                lazy[node] += val
                return
            push_down(node, l, r)
            mid = (l + r) // 2
            update(2 * node, l, mid, ql, qr, val)
            update(2 * node + 1, mid + 1, r, ql, qr, val)
 
        def query(node, l, r, pos):
            if l == r: return tree[node]                # point query at leaf
            push_down(node, l, r)
            mid = (l + r) // 2
            return query(2 * node, l, mid, pos) if pos <= mid else query(2 * node + 1, mid + 1, r, pos)
 
        for L, R, d in shifts:
            update(1, 0, n - 1, L, R, 1 if d == 1 else -1)
 
        return ''.join(
            chr((ord(c) - ord('a') + query(1, 0, n - 1, i)) % 26 + ord('a'))
            for i, c in enumerate(s)
        )

Complexity: Difference array: O(n + q) time, O(n) space — optimal. Segment tree: O((n + q) log n) time, O(n) space — useful only when intermediate queries are required.

Common Mistakes#

1. Forgetting the n + 1 sentinel slot. diff[R + 1] -= v writes one past the end when R = n - 1. Allocate n + 1, not n, or you get an out-of-bounds access.
2. Mixing inclusive / exclusive endpoints. The shift range is inclusive on both ends. The diff stamp is diff[L] += v and diff[R + 1] -= v. Using diff[R] -= v truncates by one position.
3. Negative modulo bugs in JavaScript and C++. (-1) % 26 is -1 in those languages, not 25. Always wrap with ((x % 26) + 26) % 26.
4. Reaching for a segment tree first. This is the over-engineering trap. When all updates precede all queries, the diff array is strictly faster. Pattern-match before coding.
5. Resetting running per shift. The running shift is cumulative across the entire array. Resetting it per character or per shift breaks the prefix sum.
6. Storing characters as letters during shifts. Convert to integer offsets, accumulate, then convert back. Mixing letter arithmetic mid-loop invites off-by-one in the character math.

Interview Tips#

• Pattern-match the workload. "All updates first, then one read pass — that is the difference-array signal." Saying this out loud earns credit before any code.
• Walk through the diff stamp argument. Show why diff[L] += v and diff[R + 1] -= v, then prefix sum, restores the original update.
• Mention the lazy segment tree only as the general tool. "If queries were interleaved I would use a segment tree with lazy propagation, but offline updates make the diff array strictly better."
• Handle the modulo edge case explicitly. Mention negative modulo in non-Python languages — that detail signals production experience.
• Test boundary inputs. Shifts of length 1, shifts that span the whole string, all-backward shifts, mixed directions on the same range.

Follow-up Questions#

1. Range increment with online point queries. Use a Fenwick Tree on the diff array — point query becomes prefix sum, O(log n) per query.
2. Range increment with online range queries. Use a segment tree with lazy propagation, or two Fenwick trees with the difference-of-prefix trick.
3. Range assign instead of range add. Diff array no longer applies; use a segment tree with lazy propagation or interval-painting structures.
4. Shifts on a circular string. Apply mod n to the indices, treat as a regular array.
5. Multiple alphabets / Unicode. Replace the 26 with the appropriate alphabet size and lookup table.
6. 2D version: range increment on a grid. Use a 2D difference array with four corner stamps and a 2D prefix sum sweep.

Key Takeaways#

• The difference array trick turns range increments into two O(1) stamps, then a single prefix-sum sweep recovers the final values — total O(n + q) when there are no intermediate queries.
• Use this pattern whenever the workload is offline range updates followed by a single read pass. It strictly dominates segment-tree solutions for this profile.
• Allocate n + 1 slots so diff[R + 1] -= v is always in bounds.
• Watch for negative modulo in non-Python languages; wrap with ((x % m) + m) % m to stay positive.
• Reach for a segment tree with lazy propagation only when you need queries interleaved with updates, or for range-assign updates that the diff trick cannot handle.
• The same scaffold extends to 2D difference arrays for grid range-increment problems and to BIT-based online range-add point-query systems.