Shifting Letters II - Solution & Explanation
Problem Statement
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 <= 1sconsists of lowercase English letters.
Approach Overview
Problem Overview: You receive a lowercase string s and several shift operations. Each operation specifies a range [l, r] and a direction. All characters in that range shift forward or backward in the alphabet. After applying every operation, return the final string.
Approach 1: Direct Simulation (O(n * m) time, O(1) space)
The most straightforward method applies each shift operation directly to the affected substring. For every query, iterate from l to r and update each character by shifting it forward or backward using modular arithmetic ((c - 'a' ± 1) % 26). This mirrors the problem statement and is easy to implement. The drawback is performance: if the string length is n and there are m operations, each potentially touching up to n characters, the worst‑case runtime becomes O(n * m). This works for small inputs but quickly becomes too slow when both the string and the number of operations are large. It mainly helps verify correctness before optimizing.
Approach 2: Prefix Sum Array (O(n + m) time, O(n) space)
A more efficient solution treats shifts like range updates. Instead of updating every character immediately, record the effect of each operation using a difference array. For a forward shift on [l, r], add +1 at index l and -1 at r + 1. For a backward shift, apply -1 and +1. After processing all operations, compute a running prefix sum to determine the total shift affecting each position. Then apply the final shift to each character using modulo 26. This converts repeated range updates into constant‑time operations and processes the string only once. The technique is a classic use of a prefix sum difference array and works especially well for problems involving many range modifications.
During the final pass, convert each character to its numeric position, apply the accumulated shift (handling negative values with modulo), and map it back to a letter. The algorithm touches each query once and each character once, giving O(n + m) time complexity and O(n) extra space.
Recommended for interviews: The prefix sum approach is what interviewers expect. It demonstrates recognition of range‑update patterns and efficient use of arrays. The brute-force simulation shows you understand the problem mechanics, but the optimized solution proves you can reduce repeated work using prefix accumulation techniques often seen in string and array manipulation problems.
Approach 1: Prefix Sum Array
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.
Complexity
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.
Approach 2: Direct Simulation
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.
Complexity
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 3: Default Approach
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| 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. |
| Default Approach | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Direct Simulation | O(n * m) | O(1) | Small inputs or quick baseline implementation to verify correctness |
| Prefix Sum Array (Difference Array) | O(n + m) | O(n) | Large number of range updates where applying shifts individually would be too slow |
Video Solution
Shifting Letters II | Leetcode 2381 | Difference Array Technique: Concepts & Questions - 2 | MIK • codestorywithMIK • 22,246 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Shifting Letters II easy or hard?
Shifting Letters II Python/Java solution
How to solve Shifting Letters II in O(n)?
What is the best approach for Shifting Letters II?
Is Shifting Letters II asked at Google/Amazon/Meta?
What data structure is used in Shifting Letters II?
What is the time complexity of Shifting Letters II?
Ready to solve this problem?
Practice Shifting Letters II with our built-in code editor and test cases.
Practice on FleetCode