521. Shifting Letters
You are given a lowercase string s and an integer array shifts of the same length. Shifting a letter means moving it forward in the alphabet, wrapping around at the end: shifting a once gives b, and shifting z once wraps to a.
The array is applied as a sequence of operations: for each index i, operation i shifts every letter in the prefix s[0..i] (the first i + 1 characters) forward shifts[i] times. All operations are performed, in any order — they commute.
Return the string that remains after every operation has been applied.
Note that the shift amounts can be huge (up to 10^9 each), so think about wrap-around and overflow early.
Example 1:
Input: s = "abc", shifts = [3, 5, 9]
Output: "rpl"
Explanation: Letter 0 is shifted by every operation: 3 + 5 + 9 = 17, and a + 17 = r. Letter 1 gets 5 + 9 = 14, b + 14 = p. Letter 2 gets only 9, c + 9 = l.
Example 2:
Input: s = "aaa", shifts = [1, 2, 3]
Output: "gfd"
Explanation: The letters receive totals of 6, 5 and 3 respectively: a+6 = g, a+5 = f, a+3 = d.
Constraints:
- 1 ≤ s.length ≤ 10⁵
- s consists of lowercase English letters.
- shifts.length == s.length
- 0 ≤ shifts[i] ≤ 10⁹
Hints:
Work out how many times each individual letter is shifted in total. Letter i sits inside the prefixes of operations i, i+1, …, n−1 — so its total is shifts[i] + shifts[i+1] + … + shifts[n−1], a suffix sum.
Sweep from the right, accumulating a running suffix total. Keep it reduced modulo 26 as you go: 10^5 values of 10^9 overflow 32-bit integers, but (total % 26) is all a letter ever needs.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: s = "abc", shifts = [3, 5, 9]
Expected output: "rpl"