You are given a string s of lowercase English letters and a 2D integer array shifts where shifts[i] = [starti, endi, directioni]. For every i, shift the characters in s from the index starti to the index endi (inclusive) forward if directioni = 1, or shift the characters backward if directioni = 0.
Shifting a character forward means replacing it with the next letter in the alphabet (wrapping around so that 'z' becomes 'a'). Similarly, shifting a character backward means replacing it with the previous letter in the alphabet (wrapping around so that 'a' becomes 'z').
Return the final string after all such shifts to s are applied.
Example 1:
Input: s = "abc", shifts = [[0,1,0],[1,2,1],[0,2,1]] Output: "ace" Explanation: Firstly, shift the characters from index 0 to index 1 backward. Now s = "zac". Secondly, shift the characters from index 1 to index 2 forward. Now s = "zbd". Finally, shift the characters from index 0 to index 2 forward. Now s = "ace".
Example 2:
Input: s = "dztz", shifts = [[0,0,0],[1,1,1]] Output: "catz" Explanation: Firstly, shift the characters from index 0 to index 0 backward. Now s = "cztz". Finally, shift the characters from index 1 to index 1 forward. Now s = "catz".
Constraints:
1 <= s.length, shifts.length <= 5 * 104shifts[i].length == 30 <= starti <= endi < s.length0 <= directioni <= 1s consists of lowercase English letters.The goal is to apply each shift efficiently without repeatedly modifying the string. To achieve this, we'll use a technique called the prefix sum array. We create an array of integers to store the net effect of shifts over the string indices without actually applying them. Finally, after processing all shifts, we apply the accumulated shift values to the string.
For each shift operation, modify the prefix sum array to reflect the net increase or decrease over the specified range, taking care of boundaries using a starting index and an ending index + 1. This operation ensures that when we later iterate over the string, we only need to check each position once, leading to an efficient O(n + m) complexity.
This solution uses the prefix sum array method. We begin by initializing an array to keep track of our shifts. By iterating through the shifts, we update the prefix sum array based on whether the shift is forward or backward. After processing the shifts, we iterate through the string and apply the accumulated shifts stored in the prefix sum array to achieve the final shifted string.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n + m), where n is the length of the string and m is the number of shift operations.
Space Complexity: O(n), used for the prefix sum array.
A direct simulation of the shift operation can be implemented. Given each shift description, we can directly modify the string as soon as we process a shift command, iterating over the affected range and shifting characters forward or backward based on the direction specified. This approach is simple but can be less optimal due to the repetitive iteration over the string for each shift.
This implementation involves directly iterating over the specified indices of the given string for each shift operation, altering the characters based on the direction specified in the shift. While easy to understand, this approach involves much redundant computation, making it less efficient for larger inputs.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n * m), where n is the length of the string and m is the number of shift operations.
Space Complexity: O(1), since no extra space other than input is used.
| Approach | Complexity |
|---|---|
| Prefix Sum Array | Time Complexity: O(n + m), where n is the length of the string and m is the number of shift operations. |
| Direct Simulation | Time Complexity: O(n * m), where n is the length of the string and m is the number of shift operations. |
Shifting Letters II - Leetcode 2381 - Python • NeetCodeIO • 13,456 views views
Watch 9 more video solutions →Practice Shifting Letters II with our built-in code editor and test cases.
Practice on FleetCode