Shifting Letters II solution and explanation
Google
9 more videos on this problem
Shifting Letters II | Leetcode 2381 | Difference Array Technique: Concepts & Questions - 2 | MIKcodestorywithMIK · 36:24 · 22K views
Shifting Letters II - Leetcode 2381 - PythonNeetCodeIO · 19:07 · 15K views
Shifting Letters II | Leetcode 2381Techdose · 16:41 · 8K views
2381. Shifting Letters II | Line Sweep | Prefix Sums for Range Sums/Range ImpactAryan Mittal · 15:35 · 3K views
2381. Shifting Letters II | leetcode daily challenge | dsa | shashcode | javaShashCode · 13:44 · 3K views
@Leetcode Shifting Letters II | LeetCode Solution ExplainedAlgoWizard · 10:30 · 2K views
Biweekly Contest 85 | 2381. Shifting Letters IIcodingMohan · 13:02 · 2K views
2381. Shifting Letters II (Leetcode Medium)Programming Live with Larry · 9:21 · 1K views
Shifting Letters II| LeetCode 2381| Line Sweep | leetcode potd| commulative sum |Range based top DSACode Thoughts · 17:10 · 847 views
【每日一题】LeetCode 2381. Shifting Letters IIHuifeng Guan · 13:20 · 528 views
The problem
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.
def shift_string(s, shifts):
n = len(s)
shift_values = [0] * (n + 1)
for start, end, direction in shifts:
if direction == 0:
shift_values[start] -= 1
shift_values[end + 1] += 1
else:
shift_values[start] += 1
shift_values[end + 1] -= 1
shift_sum = 0
s = list(s)
for i in range(n):
shift_sum += shift_values[i]
s[i] = chr((ord(s[i]) - ord('a') + shift_sum + 26) % 26 + ord('a'))
return ''.join(s)
# Example usage:
s = "abc"
shifts = [[0, 1, 0], [1, 2, 1], [0, 2, 1]]
print(shift_string(s, shifts)) # Output: "ace"import java.util.*;
class Solution {
public String shiftingLetters(String s, int[][] shifts) {
int n = s.length();
int[] shift_values = new int[n + 1];
for (int[] shift : shifts) {
int start = shift[0];
int end = shift[1];
int direction = shift[2];
if (direction == 0) {
shift_values[start] -= 1;
shift_values[end + 1] += 1;
} else {
shift_values[start] += 1;
shift_values[end + 1] -= 1;
}
}
int shift_sum = 0;
char[] sArray = s.toCharArray();
for (int i = 0; i < n; ++i) {
shift_sum += shift_values[i];
sArray[i] = (char) ('a' + (sArray[i] - 'a' + shift_sum + 26) % 26);
}
return new String(sArray);
}
public static void main(String[] args) {
Solution sol = new Solution();
int[][] shifts = {{0, 1, 0}, {1, 2, 1}, {0, 2, 1}};
String s = "abc";
System.out.println(sol.shiftingLetters(s, shifts)); // Output: "ace"
}
}#include <iostream>
#include <vector>
#include <string>
std::string shiftString(std::string s, std::vector<std::vector<int>>& shifts) {
int n = s.size();
std::vector<int> shift_values(n + 1, 0);
for (const auto& shift : shifts) {
int start = shift[0];
int end = shift[1];
int direction = shift[2];
if (direction == 0) {
shift_values[start] -= 1;
shift_values[end + 1] += 1;
} else {
shift_values[start] += 1;
shift_values[end + 1] -= 1;
}
}
int shift_sum = 0;
for (int i = 0; i < n; ++i) {
shift_sum += shift_values[i];
s[i] = 'a' + (s[i] - 'a' + shift_sum + 26) % 26;
}
return s;
}
int main() {
std::string s = "abc";
std::vector<std::vector<int>> shifts = {{0, 1, 0}, {1, 2, 1}, {0, 2, 1}};
std::cout << shiftString(s, shifts) << std::endl; // Output: "ace"
return 0;
}function shiftString(s, shifts) {
const n = s.length;
const shift_values = Array(n + 1).fill(0);
for (const [start, end, direction] of shifts) {
if (direction === 0) {
shift_values[start] -= 1;
shift_values[end + 1] += 1;
} else {
shift_values[start] += 1;
shift_values[end + 1] -= 1;
}
}
let shift_sum = 0;
s = [...s];
for (let i = 0; i < n; ++i) {
shift_sum += shift_values[i];
s[i] = String.fromCharCode((s[i].charCodeAt(0) - 'a'.charCodeAt(0) + shift_sum + 26) % 26 + 'a'.charCodeAt(0));
}
return s.join('');
}
// Example usage:
const s = "abc";
const shifts = [[0, 1, 0], [1, 2, 1], [0, 2, 1]];
console.log(shiftString(s, shifts)); // Output: "ace"#include <stdio.h>
#include <string.h>
void shiftString(char* s, int sSize, int shifts[][3], int shiftsSize, int* shiftsColSize) {
int accumulatedShifts[sSize + 1];
memset(accumulatedShifts, 0, sizeof(accumulatedShifts));
for (int i = 0; i < shiftsSize; i++) {
int start = shifts[i][0];
int end = shifts[i][1];
int direction = shifts[i][2];
if (direction == 0) {
accumulatedShifts[start] -= 1;
accumulatedShifts[end + 1] += 1;
} else {
accumulatedShifts[start] += 1;
accumulatedShifts[end + 1] -= 1;
}
}
int shiftValue = 0;
for (int i = 0; i < sSize; i++) {
shiftValue += accumulatedShifts[i];
s[i] = 'a' + ((s[i] - 'a' + shiftValue + 26) % 26);
}
}
int main() {
char s[] = "abc";
int shifts[3][3] = {{0, 1, 0}, {1, 2, 1}, {0, 2, 1}};
int shiftsColSize[] = {3, 3, 3};
shiftString(s, strlen(s), shifts, 3, shiftsColSize);
printf("%s\n", s); // Output: "ace"
return 0;
}using System;
public class Solution {
public string ShiftingLetters(string s, int[][] shifts) {
int n = s.Length;
int[] shiftValues = new int[n + 1];
foreach (var shift in shifts) {
int start = shift[0];
int end = shift[1];
int direction = shift[2];
if (direction == 0) {
shiftValues[start] -= 1;
shiftValues[end + 1] += 1;
} else {
shiftValues[start] += 1;
shiftValues[end + 1] -= 1;
}
}
int shiftSum = 0;
char[] result = s.ToCharArray();
for (int i = 0; i < n; ++i) {
shiftSum += shiftValues[i];
result[i] = (char)('a' + (result[i] - 'a' + shiftSum + 26) % 26);
}
return new string(result);
}
public static void Main() {
Solution sol = new Solution();
int[][] shifts = new int[][] {
new int[] {0, 1, 0},
new int[] {1, 2, 1},
new int[] {0, 2, 1}
};
string s = "abc";
Console.WriteLine(sol.ShiftingLetters(s, shifts)); // Output: "ace"
}
}The Python solution uses a straightforward design pattern, taking advantage of list comprehension and Python's built-in capabilities to handle string manipulations, efficiently applying the calculated shifts to produce the final result.
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 shift values 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.
def shift_string_direct(s, shifts):
s = list(s)
for start, end, direction in shifts:
for j in range(start, end + 1):
if direction == 0:
s[j] = chr((ord(s[j]) - ord('a') - 1 + 26) % 26 + ord('a'))
else:
s[j] = chr((ord(s[j]) - ord('a') + 1) % 26 + ord('a'))
return ''.join(s)
# Example usage:
s = "abc"
shifts = [[0, 1, 0], [1, 2, 1], [0, 2, 1]]
print(shift_string_direct(s, shifts)) # Output: "ace"import java.util.*;
class Solution {
public String shiftingLettersDirect(String s, int[][] shifts) {
char[] sArray = s.toCharArray();
for (int[] shift : shifts) {
int start = shift[0];
int end = shift[1];
int direction = shift[2];
for (int j = start; j <= end; ++j) {
if (direction == 0) {
sArray[j] = (char) ('a' + (sArray[j] - 'a' - 1 + 26) % 26);
} else {
sArray[j] = (char) ('a' + (sArray[j] - 'a' + 1) % 26);
}
}
}
return new String(sArray);
}
public static void main(String[] args) {
Solution sol = new Solution();
int[][] shifts = {{0, 1, 0}, {1, 2, 1}, {0, 2, 1}};
String s = "abc";
System.out.println(sol.shiftingLettersDirect(s, shifts)); // Output: "ace"
}
}#include <iostream>
#include <vector>
#include <string>
std::string shiftStringDirect(std::string s, std::vector<std::vector<int>>& shifts) {
for (const auto& shift : shifts) {
int start = shift[0];
int end = shift[1];
int direction = shift[2];
for (int j = start; j <= end; ++j) {
if (direction == 0) {
s[j] = 'a' + (s[j] - 'a' - 1 + 26) % 26;
} else {
s[j] = 'a' + (s[j] - 'a' + 1) % 26;
}
}
}
return s;
}
int main() {
std::string s = "abc";
std::vector<std::vector<int>> shifts = {{0, 1, 0}, {1, 2, 1}, {0, 2, 1}};
std::cout << shiftStringDirect(s, shifts) << std::endl; // Output: "ace"
return 0;
}function shiftStringDirect(s, shifts) {
s = [...s]; // Convert string to array for mutability
for (const [start, end, direction] of shifts) {
for (let j = start; j <= end; ++j) {
if (direction === 0) {
s[j] = String.fromCharCode((s[j].charCodeAt(0) - 'a'.charCodeAt(0) - 1 + 26) % 26 + 'a'.charCodeAt(0));
} else {
s[j] = String.fromCharCode((s[j].charCodeAt(0) - 'a'.charCodeAt(0) + 1) % 26 + 'a'.charCodeAt(0));
}
}
}
return s.join('');
}
// Example usage:
const s = "abc";
const shifts = [[0, 1, 0], [1, 2, 1], [0, 2, 1]];
console.log(shiftStringDirect(s, shifts)); // Output: "ace"#include <stdio.h>
#include <string.h>
void shiftStringDirect(char* s, int sSize, int shifts[][3], int shiftsSize, int* shiftsColSize) {
for (int i = 0; i < shiftsSize; i++) {
int start = shifts[i][0];
int end = shifts[i][1];
int direction = shifts[i][2];
for (int j = start; j <= end; j++) {
if (direction == 0) {
s[j] = 'a' + (s[j] - 'a' - 1 + 26) % 26;
} else {
s[j] = 'a' + (s[j] - 'a' + 1) % 26;
}
}
}
}
int main() {
char s[] = "abc";
int shifts[3][3] = {{0, 1, 0}, {1, 2, 1}, {0, 2, 1}};
int shiftsColSize[] = {3, 3, 3};
shiftStringDirect(s, strlen(s), shifts, 3, shiftsColSize);
printf("%s\n", s); // Output: "ace"
return 0;
}using System;
public class Solution {
public string ShiftingLettersDirect(string s, int[][] shifts) {
char[] result = s.ToCharArray();
foreach (var shift in shifts) {
int start = shift[0];
int end = shift[1];
int direction = shift[2];
for (int j = start; j <= end; ++j) {
if (direction == 0) {
result[j] = (char)('a' + (result[j] - 'a' - 1 + 26) % 26);
} else {
result[j] = (char)('a' + (result[j] - 'a' + 1) % 26);
}
}
}
return new string(result);
}
public static void Main() {
Solution sol = new Solution();
int[][] shifts = new int[][] {
new int[] {0, 1, 0},
new int[] {1, 2, 1},
new int[] {0, 2, 1}
};
string s = "abc";
Console.WriteLine(sol.ShiftingLettersDirect(s, shifts)); // Output: "ace"
}
}The Python solution directly applies shifts as described, highlighting the language's capability to iterate and manipulate character indices efficiently, while being easy to read and understand due to Python's expressive syntax.
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), as the processing is done in-place without additional allocations.
Approach 3: Default Approach
function shiftingLetters(s: string, shifts: number[][]): string {
const n: number = s.length;
const d: number[] = new Array(n + 1).fill(0);
for (let [i, j, v] of shifts) {
if (v === 0) {
v--;
}
d[i] += v;
d[j + 1] -= v;
}
for (let i = 1; i <= n; ++i) {
d[i] += d[i - 1];
}
let ans: string = '';
for (let i = 0; i < n; ++i) {
const j = (s.charCodeAt(i) - 'a'.charCodeAt(0) + (d[i] % 26) + 26) % 26;
ans += String.fromCharCode('a'.charCodeAt(0) + j);
}
return ans;
}func shiftingLetters(s string, shifts [][]int) string {
n := len(s)
d := make([]int, n+1)
for _, e := range shifts {
if e[2] == 0 {
e[2]--
}
d[e[0]] += e[2]
d[e[1]+1] -= e[2]
}
for i := 1; i <= n; i++ {
d[i] += d[i-1]
}
ans := []byte{}
for i, c := range s {
j := (int(c-'a') + d[i]%26 + 26) % 26
ans = append(ans, byte('a'+j))
}
return string(ans)
}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 | – |
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 |
Frequently asked questions
Is Shifting Letters II easy or hard?
Shifting Letters II is rated Medium on LeetCode. The direct simulation is simple, but recognizing the prefix sum optimization for range updates is the key step that raises the difficulty.
Shifting Letters II Python/Java solution
Most implementations convert the string into a mutable array of characters, build a difference array for shifts, compute the prefix sum, and apply modulo 26 adjustments. The same logic works across Python, Java, C++, and JavaScript with minor syntax differences.
How to solve Shifting Letters II in O(n)?
Use a difference array to record range updates. For each operation, add +1 or -1 at the start index and subtract the same value at r + 1. After processing all operations, compute a prefix sum to get the net shift for each position and apply it to the characters using modulo 26 arithmetic.
What is the best approach for Shifting Letters II?
The prefix sum (difference array) approach is the most efficient solution. Each shift operation updates only two indices, and a final prefix sum determines the total shift for every character. This reduces the complexity to O(n + m) instead of applying each shift individually.
Is Shifting Letters II asked at Google/Amazon/Meta?
Range update problems using prefix sums and difference arrays frequently appear in interviews at companies like Amazon, Google, and Meta. Variants involving range increments, interval operations, or cumulative updates test the same underlying concept used in this problem.
What data structure is used in Shifting Letters II?
The optimal solution uses an array as a difference array combined with prefix sum computation. This structure efficiently aggregates multiple range updates and then applies them to the string in a single pass.
What is the time complexity of Shifting Letters II?
The optimal prefix sum solution runs in O(n + m) time, where n is the string length and m is the number of shift operations. Each query updates a difference array in constant time, and a single pass computes the final shifts. Space complexity is O(n).