Shifting Letters: Suffix Sum for Character Shifts

You are given a string s and an integer array shifts of the same length. For each shifts[i], you shift the first i + 1 letters of s by shifts[i] positions in the alphabet (wrapping from 'z' back to 'a'). Return the final string after applying all shifts.

This is LeetCode 848: Shifting Letters, a medium problem that looks like it needs nested loops but can be solved in a single pass once you realize that each character's total shift is just a suffix sum of the shifts array.

Why this problem matters

Shifting Letters is a clean introduction to the suffix sum pattern. Many problems require you to figure out the cumulative effect of overlapping operations on an array or string. The brute force approach applies each shift one at a time, but recognizing that the operations overlap in a predictable way lets you collapse everything into a single pass.

This pattern shows up whenever you have range-based updates that stack on top of each other. Once you can spot it here, you will recognize it in problems like Range Addition, Corporate Flight Bookings, and other difference-array problems.

The brute force approach

The most direct approach is to apply each shift operation one at a time, shifting the first i + 1 characters for each shifts[i].

def shifting_letters_brute(s, shifts):
    s = list(s)
    for i, shift in enumerate(shifts):
        for j in range(i + 1):
            s[j] = chr((ord(s[j]) - ord('a') + shift) % 26 + ord('a'))
    return ''.join(s)

This works, but the inner loop processes up to i + 1 characters for each shift. In the worst case, that gives O(n^2) time. For inputs up to 10^5, this is too slow. The problem is that you are shifting the same characters over and over again when you could compute their total shift once.

The key insight: suffix sums

Each character at index i gets shifted by shifts[i], shifts[i + 1], ..., shifts[n - 1]. That is, every character accumulates all shifts from its own index to the end of the array. The total shift for character i is the suffix sum starting at index i.

You can build the suffix sums by starting at the rightmost element and accumulating leftward. At each step, take the running total mod 26 to keep the values small and avoid integer overflow in languages with fixed-width integers.

Walking through it step by step

Let's trace through s = "abc" and shifts = [3, 5, 9]. The answer is "rpl".

The suffix sum at each index tells you exactly how many positions to shift that character. No nested loops, no repeated work. One pass to compute the suffix sums, one pass to apply them.

The suffix sum solution

Here is the complete solution in Python:

def shifting_letters(s, shifts):
    n = len(shifts)
    total = 0
    shifts_copy = [0] * n
    for i in range(n - 1, -1, -1):
        total += shifts[i]
        shifts_copy[i] = total

    result = []
    for i in range(n):
        c = (ord(s[i]) - ord('a') + shifts_copy[i]) % 26
        result.append(chr(c + ord('a')))
    return ''.join(result)

Here is what each piece does:

1. Walk right to left through the shifts array, accumulating a running total. This builds the suffix sum for each index.
2. Store each suffix sum in shifts_copy[i]. After this loop, shifts_copy[i] holds the total number of positions character i needs to shift.
3. Apply each suffix sum to the corresponding character. Convert the character to a number (0 for 'a', 25 for 'z'), add the suffix sum, take mod 26 to wrap around the alphabet, and convert back to a character.
4. Join the result list into a string and return it.

Complexity analysis

You need to visit every shift and every character exactly once, so O(n) time is optimal. The result string requires O(n) space. You could avoid the separate shifts_copy array by accumulating in place, but the result string itself still requires O(n).

Building blocks

This problem is built on two reusable patterns that CodeBricks drills independently.

1. Suffix sums

The suffix sum of an array at index i is the sum of all elements from index i to the end. You compute it with a single right-to-left pass:

total = 0
for i in range(n - 1, -1, -1):
    total += arr[i]
    suffix[i] = total

This is the mirror image of prefix sums. Prefix sums answer "what is the sum of everything before index i?" while suffix sums answer "what is the sum of everything from index i onward?" Both are computed in O(n) time and are foundational building blocks for range query and range update problems.

2. Modular arithmetic

When shifting characters in the alphabet, you use (position + shift) % 26 to wrap around. This prevents going past 'z' and keeps values in the valid range. The same idea applies to rotating arrays, circular buffers, and any problem where values wrap around a fixed range.

Edge cases

Before submitting, make sure your solution handles these:

• All zero shifts [0, 0, 0]: no character moves. The output equals the input.
• Single character s = "z", shifts = [1]: 'z' wraps to 'a'. The mod 26 handles this naturally.
• Large shifts shifts = [1000000000]: the shift mod 26 is what matters. Without mod, you could overflow in some languages.
• All same characters s = "aaa", shifts = [1, 2, 3]: suffix sums are [6, 5, 3], giving "gfa".
• Wrapping around multiple times shifts = [26, 52, 78]: each of these is a multiple of 26, so no character actually changes.

From understanding to recall

You have read the suffix sum solution and it makes sense. One loop right to left to accumulate shifts, one loop left to right to build the result. But can you write it from scratch in an interview without looking at it?

The details matter: iterating right to left for the suffix sum, applying mod 26 at each step, converting between characters and integers with ord and chr. These are small but critical, and they are easy to get wrong under pressure if you have not practiced writing them from memory.

Spaced repetition closes that gap. You practice writing the suffix sum loop and the character shift logic from scratch at increasing intervals. After a few rounds, the pattern is automatic. You see "cumulative range updates" and the code flows out without hesitation.

Related posts

• Rotate Array - Another problem where modular arithmetic prevents overflow
• Product of Array Except Self - Prefix/suffix decomposition pattern
• Add Binary - Working with character manipulation and carries

CodeBricks breaks the shifting letters LeetCode problem into its suffix sum and modular arithmetic building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a suffix sum question shows up in your interview, you do not think about it. You just write it.