Shifting Letters II
Problem
You are given a string s of lowercase letters and a list of shifts shifts[i] = [start, end, direction]. For each shift, every character from index start to end (inclusive) moves one letter forward in the alphabet when direction = 1 (with 'z' wrapping to 'a'), or one letter backward when direction = 0 (with 'a' wrapping to 'z'). Return the final string after every shift is applied.
s = "abc", shifts = [[0,1,0],[1,2,1],[0,2,1]]"ace"def shiftingLetters(s, shifts):
n = len(s)
diff = [0] * (n + 1) # difference array
for start, end, direction in shifts:
amt = 1 if direction == 1 else -1
diff[start] += amt # open the range
diff[end + 1] -= amt # close just past the end
res = []
cur = 0
for i in range(n):
cur += diff[i] # prefix sum = net shift at i
nc = (ord(s[i]) - ord('a') + cur) % 26
res.append(chr(ord('a') + nc))
return "".join(res)function shiftingLetters(s, shifts) {
const n = s.length;
const diff = new Array(n + 1).fill(0); // difference array
for (const [start, end, direction] of shifts) {
const amt = direction === 1 ? 1 : -1;
diff[start] += amt; // open the range
diff[end + 1] -= amt; // close just past the end
}
const res = [];
let cur = 0;
for (let i = 0; i < n; i++) {
cur += diff[i]; // prefix sum = net shift
const nc = ((s.charCodeAt(i) - 97 + cur) % 26 + 26) % 26;
res.push(String.fromCharCode(97 + nc));
}
return res.join("");
}String shiftingLetters(String s, int[][] shifts) {
int n = s.length();
long[] diff = new long[n + 1]; // difference array
for (int[] sh : shifts) {
int amt = sh[2] == 1 ? 1 : -1;
diff[sh[0]] += amt; // open the range
diff[sh[1] + 1] -= amt; // close just past the end
}
char[] res = new char[n];
long cur = 0;
for (int i = 0; i < n; i++) {
cur += diff[i]; // prefix sum = net shift
int nc = (int) (((s.charAt(i) - 'a' + cur) % 26 + 26) % 26);
res[i] = (char) ('a' + nc);
}
return new String(res);
}string shiftingLetters(string s, vector<vector<int>>& shifts) {
int n = s.size();
vector<long long> diff(n + 1, 0); // difference array
for (auto& sh : shifts) {
int amt = sh[2] == 1 ? 1 : -1;
diff[sh[0]] += amt; // open the range
diff[sh[1] + 1] -= amt; // close just past the end
}
long long cur = 0;
for (int i = 0; i < n; i++) {
cur += diff[i]; // prefix sum = net shift
int nc = ((s[i] - 'a' + cur) % 26 + 26) % 26;
s[i] = 'a' + nc;
}
return s;
}Explanation
A naive solution would walk every index of every shift and bump each letter one at a time. With up to 5·10⁴ shifts each spanning up to 5·10⁴ characters, that is quadratic and far too slow. The trick is to realize only the net shift of each index matters — and net shifts add up.
We use a difference array diff of length n + 1. A forward shift contributes +1, a backward shift contributes -1. For a shift covering [start, end] we do diff[start] += amt and diff[end + 1] -= amt. This marks where the effect begins and where it ends, in O(1) per shift instead of touching every index.
Then a single prefix sum over diff reconstructs the total shift at each position: cur += diff[i] gives the cumulative amount that applies to index i. Because every +1 and -1 we placed earlier flows forward through the running sum, ranges that overlap simply combine.
Finally we apply each net shift modulo 26 to wrap around the alphabet. Since cur can be negative, we use ((value % 26) + 26) % 26 to keep the result in 0..25 before turning it back into a letter.
For s = "abc" with shifts [[0,1,0],[1,2,1],[0,2,1]] the net shifts come out to [0, +1, +2], producing "ace" — and we computed it in one pass instead of replaying every range.