Shifting Letters — Solution in Python, Java & C++
Shifting Letters solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem on arrays and strings.
Shifting Letters is a medium coding problem on arrays, strings and prefix sum, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Arrays, Strings, Prefix Sum
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given a lowercase string s and an integer array shifts of the same length.
Shifting a letter moves it to the next letter of the alphabet, wrapping around so that 'z' becomes 'a'. For every i, shift the first i + 1 letters of s by shifts[i] positions.
Return the string after all the shifts have been applied.
Example 1
Input: s = "kai", shifts = [1,2,3]
Output: qfl
Explanation: Letter 0 is shifted 1 + 2 + 3 = 6 times, letter 1 is shifted 2 + 3 = 5 times, letter 2 is shifted 3 times.
Example 2
Input: s = "zz", shifts = [1,26]
Output: az
Explanation: The first `z` moves 27 positions — one full lap plus one.
Example 3
Input: s = "a", shifts = [1000000000]
Output: m
Explanation: 10^9 leaves remainder 12 when divided by 26.
Constraints
1 <= s.length <= 10^5s consists of lowercase English lettersshifts.length == s.length0 <= shifts[i] <= 10^9
Hints for Shifting Letters
Hint 1
Letter
iis affected byshifts[i],shifts[i + 1], …,shifts[n - 1]— every shift whose prefix covers it.Hint 2
So letter
imoves by the suffix sum ofshiftsstarting ati. Walk from the right to build it in one pass.Hint 3
The sums can reach 10^14, but only their value modulo 26 matters — reduce as you go.
How to solve Shifting Letters
The total shift applied to position i is shifts[i] + shifts[i + 1] + … + shifts[n - 1], so one right-to-left pass keeping a running sum modulo 26 shifts every letter.
Approach
- Set
total = 0. - For
ifromn - 1down to0:total = (total + shifts[i]) mod 26, then replaces[i]with the letter(s[i] - 'a' + total) mod 26places after'a'. - Return the rebuilt string.
Why it works
The operation for index j touches letters 0..j, so letter i receives exactly the shifts with j >= i. Shifting by x and by x mod 26 land on the same letter because the alphabet wraps every 26 steps.
Complexity
- Time —
O(n) - Space —
O(n) for the output string
Pitfalls
- Without the modulo the running sum overflows 32-bit integers (10^5 · 10^9).
- Shifting prefixes one by one is
O(n^2)and too slow forn = 10^5.
Reference solution
Python
from typing import List
def shiftingLetters(s: str, shifts: List[int]) -> str:
out = list(s)
total = 0
for i in range(len(s) - 1, -1, -1):
total = (total + shifts[i]) % 26
out[i] = chr(97 + (ord(s[i]) - 97 + total) % 26)
return "".join(out)Java
public static String shiftingLetters(String s, int[] shifts) {
char[] out = s.toCharArray();
int total = 0;
for (int i = out.length - 1; i >= 0; i--) {
total = (total + shifts[i] % 26) % 26;
out[i] = (char) ('a' + (out[i] - 'a' + total) % 26);
}
return new String(out);
}C++
string shiftingLetters(string s, vector<int>& shifts) {
int total = 0;
for (int i = (int) s.size() - 1; i >= 0; i--) {
total = (total + shifts[i] % 26) % 26;
s[i] = (char) ('a' + (s[i] - 'a' + total) % 26);
}
return s;
}JavaScript
var shiftingLetters = function(s, shifts) {
var out = new Array(s.length);
var total = 0;
for (var i = s.length - 1; i >= 0; i--) {
total = (total + shifts[i]) % 26;
out[i] = String.fromCharCode(97 + (s.charCodeAt(i) - 97 + total) % 26);
}
return out.join("");
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.