← DSA Atlas
Dedicated problem page · #2381

Shifting Letters II

MediumPrefix Sum and Difference ArrayRange-update via difference arrayDifference array + prefix sum with modular arithmetic
Solve on LeetCode ↗
2381
MediumPrefix Sum and Difference ArrayDifference array + prefix sum with modular arithmeticRange-update via difference array

Shifting Letters II

You are given a string s of lowercase English letters and a 2D array shifts where shifts[i] = [start, end, direction]. For each shift, if direction == 1 shift every character in s from index start to end (inclusive) forward one letter (wrapping 'z' to 'a'); if direction == 0 shift them backward one letter (wrapping 'a' to 'z'). Return the final string after applying all shifts.

Open official problem prompt ↗
In plain English

Determine the net letter offset applied to each character after many overlapping forward/backward range shifts, then rebuild the final string efficiently.

Picture it like this

Like a row of dials on a combination lock: each instruction nudges a contiguous block of dials up or down. Rather than turning every dial for every instruction, you tally the net turns per dial and spin each one just once at the end.

Example
Input
s = "abc", shifts = [[0,1,0],[1,2,1],[0,2,1]]
Output
"ace"
Why
Net shifts are [0, +1, +2]: 'a' stays 'a', 'b'->'c', 'c'->'e', giving "ace".
Constraints
1 <= s.length, shifts.length <= 5 * 10^4shifts[i].length == 30 <= start_i <= end_i < s.length0 <= direction_i <= 1s consists of lowercase English letters
Pattern lesson

See the pattern, then code

Range-update via difference array
Recognition clue

Repeated add/subtract-one over character index ranges, then a single final read, is a difference-array signal; the alphabet wrap adds a modulo-26 step.

↗
Prefix Sum and Difference Array

Repeated range queries, subarray totals, balanced counts, or batched range updates.. A forward shift is +1 and a backward shift is -1 on a character's net offset. Accumulating these per index is another range-update problem, so record each shift as two endpoint deltas and prefix-sum to get every character's net offset at once.

New words, made simpleKnow these before the algorithm
Difference array
An array of deltas whose prefix sum reconstructs per-index totals, ideal for many range updates.
Modular arithmetic
Wrapping values into a fixed range; here mod 26 keeps shifts within the 26-letter alphabet.
Net shift
The signed sum of all forward (+1) and backward (-1) shifts that land on a given index.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Apply each shift directly

Up to 5*10^4 shifts over 5*10^4 characters is ~2.5*10^9 operations, far too slow.

For every shift, loop start..end and increment/decrement each character.

Time O(n * m)Space O(n)
Best choiceDifference array + prefix sum + mod 26

Constant work per shift and two linear passes; comfortably within limits.

Record +/-1 at range endpoints, prefix-sum for net shifts, then rotate each letter once modulo 26.

Time O(n + m)Space O(n)
The rule we keep true

Invariant

After all shifts are recorded, the prefix sum of diff up to index i equals the net (signed) number of forward shifts applied to character i.

Why this is correct

Reasoning

Each shift contributes +1 or -1 uniformly across [start, end]. Encoding it as +amount at start and -amount at end+1 makes the prefix sum carry that amount exactly across the intended range and cancel it afterward. Because the alphabet is cyclic, only the net offset modulo 26 matters, and Python's % on the possibly-negative running value plus the final % 26 keep every result a valid lowercase letter.

The algorithm in three movesSay these aloud before coding
1Build a diff array of size len(s) + 1

diff = [0, 1, 1, -2]

2For each shift, set amount = +1 if direction is 1 else -1, add it at start and subtract it at end+1

net shifts = [0, 1, 2]

3Prefix-sum diff to get the net shift per index

'abc' -> 'ace'

4Rotate each character by (net shift mod 26), keeping it in range 'a'..'z'

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
00
11
12
-23
1 · Readstart=0, end=1, dir=0 -> amount=-1
2 · AskWhere to mark deltas?
3 · Update statediff = [-1, 0, 1, 0]
4 · Result-1 at index 0, +1 at index 2
Key takeaway

The difference array over indices 0..3; its prefix sum yields net shifts [0, 1, 2].

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 4Difference array of size n + 1

    The extra slot absorbs the -amount mark at end+1 when end is the last index.

  2. 2
    Lines 5-8Record each shift in O(1)

    Direction 1 means +1, direction 0 means -1; add at start, cancel at end+1.

  3. 3
    Lines 9-14Prefix sum then rotate

    running holds the net shift; (ord(c)-97+shift) % 26 + 97 rotates the letter cyclically and stays within 'a'..'z'.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • All shifts backward on the same range (net negative offsets)
  • Shifts whose net offset is a multiple of 26 (character unchanged)
  • A single-character range where start == end
  • Wrapping at the alphabet boundary, e.g. 'z' forward to 'a' or 'a' backward to 'z'
!

Common beginner mistakes

  • Forgetting to apply mod 26, so large accumulated shifts overflow the alphabet
  • Mishandling negative net shifts; relying on a manual (x - shift) without a proper modulo can produce characters below 'a' — normalize with % 26 first
  • Marking the cancel at end instead of end+1, which under-shifts the last character in each range
  • Treating direction 0 as +1 by mistake
Check your understanding

After the prefix sum, running can be negative (many backward shifts). Why does chr((ord(s[i]) - 97 + running % 26) % 26 + 97) still give a valid lowercase letter?

More in Prefix Sum and Difference Array

#303Range Sum Query – ImmutablePrecomputed prefix sums#304Range Sum Query 2D – Immutable2D precomputed prefix sums#523Continuous Subarray SumPrefix sum remainder with hash map#724Find Pivot IndexRunning prefix versus suffix balance#930Binary Subarrays With SumPrefix sum counts with hash map#1094Car PoolingDifference array over positions