Watch 10 video solutions for Shifting Letters, a medium level problem involving Array, String, Prefix Sum. This walkthrough by Timothy H Chang has 9,584 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given a string s of lowercase English letters and an integer array shifts of the same length.
Call the shift() of a letter, the next letter in the alphabet, (wrapping around so that 'z' becomes 'a').
shift('a') = 'b', shift('t') = 'u', and shift('z') = 'a'.Now for each shifts[i] = x, we want to shift the first i + 1 letters of s, x times.
Return the final string after all such shifts to s are applied.
Example 1:
Input: s = "abc", shifts = [3,5,9] Output: "rpl" Explanation: We start with "abc". After shifting the first 1 letters of s by 3, we have "dbc". After shifting the first 2 letters of s by 5, we have "igc". After shifting the first 3 letters of s by 9, we have "rpl", the answer.
Example 2:
Input: s = "aaa", shifts = [1,2,3] Output: "gfd"
Constraints:
1 <= s.length <= 105s consists of lowercase English letters.shifts.length == s.length0 <= shifts[i] <= 109Problem Overview: You are given a lowercase string s and an array shifts. Each shifts[i] means the first i + 1 characters of the string should be shifted forward in the alphabet that many times (wrapping around after 'z'). The task is to apply all operations and return the final string.
Approach 1: Naive Prefix Simulation (O(n²) time, O(1) space)
The straightforward idea is to process every shift operation directly. For each index i, iterate from the start of the string to i and shift every character by shifts[i]. Character shifting is done with modular arithmetic using (char - 'a' + shift) % 26. While simple to reason about, this repeatedly updates the same characters and leads to quadratic work. With large inputs, this approach quickly becomes too slow.
Approach 2: Cumulative Shift Calculation (O(n) time, O(n) space)
Each character s[i] is affected by all shift values from i to the end of the array. Instead of applying operations one by one, compute a cumulative suffix sum of the shifts array. Create a prefix-sum style structure where totalShift[i] = shifts[i] + shifts[i+1] + .... Then update each character once using totalShift[i] % 26. This removes repeated work and converts the problem into a single pass over the string. The technique is a classic use of prefix sum logic applied to a array while transforming a string.
Approach 3: Optimized Backward Calculation (O(n) time, O(1) space)
The cumulative idea can be implemented without an extra array. Traverse the string from right to left while maintaining a running shift value. At each step, update runningShift = (runningShift + shifts[i]) % 26, then apply that shift to s[i]. Because every character depends on all shifts to its right, this backward traversal naturally accumulates the correct value. Each character is processed exactly once, and no additional storage is required beyond a few variables.
Recommended for interviews: Interviewers typically expect the backward cumulative solution. The naive simulation demonstrates understanding of the problem mechanics, but the optimized O(n) solution shows you recognize overlapping operations and can compress them using cumulative sums. Implementing the backward pass with modular arithmetic is both efficient and clean.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Naive Prefix Simulation | O(n²) | O(1) | Useful for understanding the shifting process or very small inputs |
| Cumulative Shift Calculation | O(n) | O(n) | When using explicit prefix/suffix sum arrays for clarity |
| Optimized Backward Calculation | O(n) | O(1) | Best production and interview solution with minimal memory usage |