726. Shifting Letters From the Right
A lowercase string of length n is given, along with n shift amounts. Shift i means:
advance the first i + 1 letters of the string forward through the alphabet by shift[i]
places, wrapping from z back to a. The shifts are applied in order, from shift[0] to
shift[n-1].
Print the final string.
abc, shifts 3 5 9 -> rpl
aaa, shifts 1 2 3 -> gfd
xyz, shifts 25 25 25 -> uwy
## Every letter is shifted by a SUFFIX total
Letter i is inside the first j + 1 letters exactly when j >= i. So its total shift is
shift[i] + shift[i+1] + ... + shift[n-1]
which is a suffix sum, not a prefix sum. Working out which end the totals accumulate from is the whole problem, and the instinct to reach for a prefix sum is exactly what the statement is testing.
Check it on abc with shifts 3 5 9: letter 0 moves by 3 + 5 + 9 = 17, so a becomes
r. Letter 2 moves by 9 alone, so c becomes l.
## The running total goes backwards
run = 0
for i from n-1 down to 0:
run = (run + shift[i]) mod 26
out[i] = letter i advanced by run
One pass, right to left, no array of suffix sums needed.
## Reduce modulo 26 as you go
The shifts total up to 2 * 10^5 times 10^9, which is 2 * 10^14. That fits in 64 bits,
but taking the remainder at every step keeps the running value under 26 and makes the whole
thing safe in 32 bits.
Shifting by a multiple of 26 leaves a letter unchanged, which is why aba with shifts
26 26 26 comes back as aba.
## The wrap
Advancing letter c by k is
'a' + (c - 'a' + k) mod 26
Because the running total is already reduced and non negative, the remainder never goes negative and no correction is needed. In a variant with negative shifts it would, and that is worth noticing now rather than later.
## Boundaries
All shifts zero returns the string unchanged. A single letter is shifted by its own amount only.
## Cost
Time O(n). Space O(n) for the output.
Constraints - `1 ≤ n ≤ 200000` - `0 ≤ each shift ≤ 10^9` - every character is a lowercase letter
Input
The first line contains the lowercase string.
The second line contains n integers, the shift amounts.
Output
Print the final string on one line, with no spaces and no trailing characters.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.