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.
In this approach, we calculate the cumulative shift for each character and apply it directly. We start from the first character and compute the required shift by summing all applicable shift values for each character position. After calculating the cumulative shift, we adjust each character in the string accordingly.
This C implementation calculates the total shift for each character by iterating through the shift array and performs letter shifting using ASCII manipulations. Remember, we're cumulatively adjusting the character based on all previous shifts.
Time Complexity: O(n^2) where n is the length of the string due to the nested loops.
Space Complexity: O(1) since no extra space other than for variables is used.
This approach optimizes the shift of letters by computing the cumulative shift from the last character to the first. It reduces the overhead of multiple summations using a single pass through the shifts array from back to front.
This C code optimizes the shift calculations by continuously adding shifts from right to left, which avoids recalculating sums repeatedly.
Time Complexity: O(n), processing each character once.
Space Complexity: O(1).
For each character in the string s, we need to calculate its final shift amount, which is the sum of shifts[i], shifts[i + 1], shifts[i + 2], and so on. We can use the concept of suffix sum, traversing shifts from back to front, calculating the final shift amount for each character, and then taking modulo 26 to get the final character.
The time complexity is O(n), where n is the length of the string s. Ignoring the space consumption of the answer, the space complexity is O(1).
| Approach | Complexity |
|---|---|
| Cumulative Shift Calculation | Time Complexity: |
| Optimized Backward Calculation | Time Complexity: |
| Suffix Sum | — |
| 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 |
Leetcode - Shifting Letters (Python) • Timothy H Chang • 9,584 views views
Watch 9 more video solutions →Practice Shifting Letters with our built-in code editor and test cases.
Practice on FleetCode