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] <= 109In 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.
C++
Java
Python
C#
JavaScript
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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), processing each character once.
Space Complexity: O(1).
| Approach | Complexity |
|---|---|
| Cumulative Shift Calculation | Time Complexity: |
| Optimized Backward Calculation | Time Complexity: |
Shifting Letters II - Leetcode 2381 - Python • NeetCodeIO • 13,456 views views
Watch 9 more video solutions →Practice Shifting Letters with our built-in code editor and test cases.
Practice on FleetCode