Shifting Letters II — Solution in Python, Java & C++
Shifting Letters II solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Shifting Letters II is a medium coding problem on arrays, strings and prefix sum, asked in Amazon, Google and Microsoft interviews.
- Difficulty: Medium
- Topics: Arrays, Strings, Prefix Sum
- Asked at: Amazon, Google, Microsoft
- 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 a list of operations shifts, where shifts[i] = [start, end, direction].
Operation i shifts every character from index start to index end (inclusive) one step forward in the alphabet when direction == 1, or one step backward when direction == 0. The alphabet wraps around: shifting 'z' forward gives 'a' and shifting 'a' backward gives 'z'.
Apply all operations and return the final string.
Example 1
Input: s = "kairo", shifts = [[0,4,1],[1,2,0]]
Output: laisp
Explanation: The first operation gives `"lbjsp"`; the second moves indices 1 and 2 back, giving `"laisp"`.
Example 2
Input: s = "az", shifts = [[0,1,1]]
Output: ba
Explanation: `'z'` wraps around to `'a'`.
Example 3
Input: s = "a", shifts = [[0,0,0],[0,0,0]]
Output: y
Constraints
1 <= s.length, shifts.length <= 5 * 10^4shifts[i].length == 30 <= start <= end < s.length0 <= direction <= 1s consists of lowercase English letters
Hints for Shifting Letters II
Hint 1
Applying each operation letter by letter is O(n·q). Only the net shift of each position matters.
Hint 2
Add +1 or -1 on a whole range at once with a difference array: mark the start, unmark just after the end.
Hint 3
A running sum over the difference array gives each position's net shift; reduce it modulo 26, taking care with negatives.
How to solve Shifting Letters II
The order of the operations does not matter, only each position's net shift. A difference array records every range update in O(1), and one prefix sum recovers the net shifts.
Approach
- Create
diffof lengthn + 1, all zeros. - For each
[start, end, direction], letv = +1ifdirection == 1else-1; dodiff[start] += vanddiff[end + 1] -= v. - Sweep
ifrom 0 ton - 1keeping a running sumcur += diff[i]; the new letter is(s[i] - 'a' + cur) mod 26, normalised into0..25.
Why it works
Shifts commute, so the final letter at position i depends only on the sum of +1/-1 over the operations covering i. The running sum of the difference array at i counts exactly the operations whose range starts at or before i and has not ended before i, which are the ones covering it.
Complexity
- Time —
O(n + q) - Space —
O(n)
Pitfalls
- The net shift can be negative: use
((x % 26) + 26) % 26in languages whose%keeps the sign. diffneeds one extra slot forend + 1 == n.- Backward is
direction == 0, not-1.
Reference solution
Python
from typing import List
def shiftingLetters(s: str, shifts: List[List[int]]) -> str:
n = len(s)
diff = [0] * (n + 1)
for a, b, d in shifts:
v = 1 if d == 1 else -1
diff[a] += v
diff[b + 1] -= v
out = []
cur = 0
for i, ch in enumerate(s):
cur += diff[i]
out.append(chr((ord(ch) - 97 + cur) % 26 + 97))
return "".join(out)Java
public static String shiftingLetters(String s, int[][] shifts) {
int n = s.length();
int[] diff = new int[n + 1];
for (int[] sh : shifts) {
int v = sh[2] == 1 ? 1 : -1;
diff[sh[0]] += v;
diff[sh[1] + 1] -= v;
}
char[] out = new char[n];
int cur = 0;
for (int i = 0; i < n; i++) {
cur += diff[i];
int x = (((s.charAt(i) - 'a' + cur) % 26) + 26) % 26;
out[i] = (char) ('a' + x);
}
return new String(out);
}C++
string shiftingLetters(string s, vector<vector<int>>& shifts) {
int n = s.size();
vector<int> diff(n + 1, 0);
for (auto& sh : shifts) {
int v = sh[2] == 1 ? 1 : -1;
diff[sh[0]] += v;
diff[sh[1] + 1] -= v;
}
int cur = 0;
for (int i = 0; i < n; i++) {
cur += diff[i];
int x = (((s[i] - 'a' + cur) % 26) + 26) % 26;
s[i] = (char)('a' + x);
}
return s;
}JavaScript
var shiftingLetters = function(s, shifts) {
var n = s.length;
var diff = new Array(n + 1).fill(0);
for (var i = 0; i < shifts.length; i++) {
var v = shifts[i][2] === 1 ? 1 : -1;
diff[shifts[i][0]] += v;
diff[shifts[i][1] + 1] -= v;
}
var out = [], cur = 0;
for (var j = 0; j < n; j++) {
cur += diff[j];
var x = (((s.charCodeAt(j) - 97 + cur) % 26) + 26) % 26;
out.push(String.fromCharCode(97 + x));
}
return out.join("");
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.