Shifting Letters solution and explanation
Google
9 more videos on this problem
Leetcode - Shifting Letters (Python)Timothy H Chang · 4:54 · 9K views
Shifting Letters | Leetcode 848 | Live coding sessionCoding Decoded · 6:31 · 3K views
花花酱 LeetCode 848. Shifting Letters - 刷题找工作 EP196Hua Hua · 9:57 · 3K views
Shifting Letters | LeetCode 848 | String | FacebookNaresh Gupta · 9:28 · 2K views
Shifting Letters | Maths | Strings | 848 LeetCode | Day 08CodeWithSunny · 9:02 · 1K views
Shifting Letters | Leetcode 848 | Strings | DSA | CPTejpratap Pandey · 8:35 · 813 views
Leetcode Problem 848 Shifting Letters (Solution Explained)JJ Ferman · 14:42 · 540 views
Daily Leetcode #526: Sep 08, 2021 - 848. Shifting LettersProgramming Live with Larry · 8:36 · 412 views
Shifting Letters leetcode 848 | Live coding sessions5 Minutes Code · 9:27 · 402 views
848. Shifting Letters - Daily Leetcode (Day 67)yeetcode · 3:27 · 347 views
The problem
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').
- For example,
shift('a') = 'b',shift('t') = 'u', andshift('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 <= 105sconsists of lowercase English letters.shifts.length == s.length0 <= shifts[i] <= 109
Approach overview
Problem 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.
Approach 1: Cumulative Shift Calculation
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.
def shifting_letters(s: str, shifts: list) -> str:
s_list = list(s)
for i in range(len(s_list)):
total_shift = sum(shifts[:i+1]) % 26
s_list[i] = chr((ord(s_list[i]) - ord('a') + total_shift) % 26 + ord('a'))
return ''.join(s_list)
print(shifting_letters('abc', [3, 5, 9]))public class ShiftingLetters {
public static String shiftingLetters(String s, int[] shifts) {
char[] chars = s.toCharArray();
for (int i = 0; i < chars.length; i++) {
int totalShift = 0;
for (int j = 0; j <= i; j++) {
totalShift += shifts[j];
}
totalShift %= 26;
chars[i] = (char)((chars[i] - 'a' + totalShift) % 26 + 'a');
}
return new String(chars);
}
public static void main(String[] args) {
String s = "abc";
int[] shifts = {3, 5, 9};
System.out.println(shiftingLetters(s, shifts));
}
}#include <iostream>
#include <vector>
using namespace std;
string shiftingLetters(string s, vector<int>& shifts) {
for (int i = 0; i < s.length(); i++) {
int totalShift = 0;
for (int j = 0; j <= i; j++) {
totalShift += shifts[j];
}
totalShift %= 26;
s[i] = (s[i] - 'a' + totalShift) % 26 + 'a';
}
return s;
}
int main() {
string s = "abc";
vector<int> shifts = {3, 5, 9};
cout << shiftingLetters(s, shifts) << endl;
return 0;
}function shiftingLetters(s, shifts) {
let result = s.split('');
for (let i = 0; i < result.length; i++) {
let totalShift = 0;
for (let j = 0; j <= i; j++) {
totalShift += shifts[j];
}
totalShift %= 26;
result[i] = String.fromCharCode((result[i].charCodeAt(0) - 97 + totalShift) % 26 + 97);
}
return result.join('');
}
console.log(shiftingLetters('abc', [3, 5, 9]));#include <stdio.h>
#include <string.h>
void shiftLetters(char *s, int *shifts, int length) {
for (int i = 0; i < length; i++) {
int total_shift = 0;
for (int j = 0; j <= i; j++) {
total_shift += shifts[j];
}
total_shift %= 26;
s[i] = (s[i] - 'a' + total_shift) % 26 + 'a';
}
}
int main() {
char s[] = "abc";
int shifts[] = {3, 5, 9};
int length = sizeof(shifts) / sizeof(shifts[0]);
shiftLetters(s, shifts, length);
printf("%s\n", s);
return 0;
}using System;
class Program {
static string ShiftingLetters(string s, int[] shifts) {
char[] result = s.ToCharArray();
for (int i = 0; i < result.Length; i++) {
int totalShift = 0;
for (int j = 0; j <= i; j++) {
totalShift += shifts[j];
}
totalShift %= 26;
result[i] = (char)((result[i] - 'a' + totalShift) % 26 + 'a');
}
return new string(result);
}
static void Main() {
string s = "abc";
int[] shifts = { 3, 5, 9 };
Console.WriteLine(ShiftingLetters(s, shifts));
}
}In Python, we employ slicing for efficient sum calculation while using list mutation to construct the final shifted result.
Time Complexity: O(n^2). Space Complexity: O(n) for storing mutable strings.
Approach 2: Optimized Backward Calculation
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.
def shifting_letters_optimized(s: str, shifts: list) -> str:
s_list = list(s)
cumulative_shift = 0
for i in range(len(s_list) - 1, -1, -1):
cumulative_shift = (cumulative_shift + shifts[i]) % 26
s_list[i] = chr((ord(s_list[i]) - ord('a') + cumulative_shift) % 26 + ord('a'))
return ''.join(s_list)
print(shifting_letters_optimized('abc', [3, 5, 9]))public class ShiftingLettersOptimized {
public static String shiftingLetters(String s, int[] shifts) {
char[] chars = s.toCharArray();
int cumulativeShift = 0;
for (int i = chars.length - 1; i >= 0; i--) {
cumulativeShift = (cumulativeShift + shifts[i]) % 26;
chars[i] = (char)((chars[i] - 'a' + cumulativeShift) % 26 + 'a');
}
return new String(chars);
}
public static void main(String[] args) {
String s = "abc";
int[] shifts = {3, 5, 9};
System.out.println(shiftingLetters(s, shifts));
}
}#include <iostream>
#include <vector>
using namespace std;
string shiftingLettersOptimized(string s, vector<int>& shifts) {
int cumulative_shift = 0;
for (int i = s.length() - 1; i >= 0; i--) {
cumulative_shift = (cumulative_shift + shifts[i]) % 26;
s[i] = (s[i] - 'a' + cumulative_shift) % 26 + 'a';
}
return s;
}
int main() {
string s = "abc";
vector<int> shifts = {3, 5, 9};
cout << shiftingLettersOptimized(s, shifts) << endl;
return 0;
}function shiftingLettersOptimized(s, shifts) {
let cumulative_shift = 0;
const result = s.split('');
for (let i = result.length - 1; i >= 0; i--) {
cumulative_shift = (cumulative_shift + shifts[i]) % 26;
result[i] = String.fromCharCode((result[i].charCodeAt(0) - 97 + cumulative_shift) % 26 + 97);
}
return result.join('');
}
console.log(shiftingLettersOptimized('abc', [3, 5, 9]));#include <stdio.h>
#include <string.h>
void shiftLettersOptimized(char *s, int *shifts, int length) {
int cumulative_shift = 0;
for (int i = length - 1; i >= 0; i--) {
cumulative_shift = (cumulative_shift + shifts[i]) % 26;
s[i] = (s[i] - 'a' + cumulative_shift) % 26 + 'a';
}
}
int main() {
char s[] = "abc";
int shifts[] = {3, 5, 9};
int length = sizeof(shifts) / sizeof(shifts[0]);
shiftLettersOptimized(s, shifts, length);
printf("%s\n", s);
return 0;
}using System;
class Program {
static string ShiftingLettersOptimized(string s, int[] shifts) {
char[] result = s.ToCharArray();
int cumulative_shift = 0;
for (int i = result.Length - 1; i >= 0; i--) {
cumulative_shift = (cumulative_shift + shifts[i]) % 26;
result[i] = (char)((result[i] - 'a' + cumulative_shift) % 26 + 'a');
}
return new string(result);
}
static void Main() {
string s = "abc";
int[] shifts = { 3, 5, 9 };
Console.WriteLine(ShiftingLettersOptimized(s, shifts));
}
}Python's solution effectively combines cumulative shift calculation in a single backward loop for optimized processing.
Time Complexity: O(n). Space Complexity: O(n).
Approach 3: Suffix Sum
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).
func shiftingLetters(s string, shifts []int) string {
t := 0
n := len(s)
cs := []byte(s)
for i := n - 1; i >= 0; i-- {
t += shifts[i]
j := (int(cs[i]-'a') + t) % 26
cs[i] = byte('a' + j)
}
return string(cs)
}Complexity comparison
| Approach | Complexity |
|---|---|
| Cumulative Shift Calculation | Time Complexity: |
| Optimized Backward Calculation | Time Complexity: |
| Suffix Sum | – |
Complexity analysis
| 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 |
Frequently asked questions
Is Shifting Letters easy or hard?
Shifting Letters is considered a medium-level problem. The main difficulty comes from recognizing that each shift affects all earlier characters. Once you realize the overlapping operations can be combined using cumulative sums, the implementation becomes straightforward.
Shifting Letters Python/Java solution
In Python or Java, the optimal implementation iterates from the end of the string while accumulating shift values modulo 26. Convert characters to numeric offsets using 'a', apply the shift, then convert back to characters. Both languages achieve O(n) time complexity with constant extra space.
How to solve Shifting Letters in O(n)?
Compute the cumulative shift while traversing from right to left. Maintain a variable runningShift and update it as runningShift = (runningShift + shifts[i]) % 26. Apply that shift to s[i] using modular arithmetic. This avoids repeated updates and transforms the problem into a single linear pass.
What is the best approach for Shifting Letters?
The optimized backward cumulative shift approach is the best solution. Traverse the string from right to left while maintaining a running shift value. Each step adds shifts[i] to the running total and applies it modulo 26 to the character. This processes every character once with O(n) time and O(1) extra space.
Is Shifting Letters asked at Google/Amazon/Meta?
Shifting Letters represents a common interview pattern involving prefix sums and string manipulation. Variations of cumulative operations on arrays or strings appear frequently in interviews at companies like Amazon, Google, and Meta, especially in medium-level coding rounds.
What data structure is used in Shifting Letters?
The problem primarily uses arrays and strings along with prefix-sum style cumulative calculations. No advanced data structures are required. Efficient solutions rely on modular arithmetic and maintaining a running suffix sum while iterating through the array.
What is the time complexity of Shifting Letters?
The optimal solution runs in O(n) time where n is the length of the string. Each character is visited exactly once while accumulating the shift values. The naive simulation approach takes O(n^2) because each shift operation repeatedly modifies earlier characters.