Shifting Letters
Problem
Given a string s and an integer array shifts of the same length, shift the first i+1 letters of s by shifts[i] (lowercase, wrapping). Return the resulting string.
s = "abc", shifts = [3,5,9]"rpl"def shiftingLetters(s, shifts):
n = len(s)
total = 0
res = list(s)
for i in range(n - 1, -1, -1):
total = (total + shifts[i]) % 26
res[i] = chr((ord(s[i]) - ord('a') + total) % 26 + ord('a'))
return "".join(res)
function shiftingLetters(s, shifts) {
const n = s.length;
let total = 0;
const res = s.split("");
for (let i = n - 1; i >= 0; i--) {
total = (total + shifts[i]) % 26;
res[i] = String.fromCharCode((s.charCodeAt(i) - 97 + total) % 26 + 97);
}
return res.join("");
}
class Solution {
public String shiftingLetters(String s, int[] shifts) {
int n = s.length();
long total = 0;
char[] res = s.toCharArray();
for (int i = n - 1; i >= 0; i--) {
total = (total + shifts[i]) % 26;
res[i] = (char) ((res[i] - 'a' + total) % 26 + 'a');
}
return new String(res);
}
}
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
string shiftingLetters(string s, vector<int>& shifts) {
long long total = 0;
for (int i = s.size() - 1; i >= 0; i--) {
total = (total + shifts[i]) % 26;
s[i] = (s[i] - 'a' + total) % 26 + 'a';
}
return s;
}
};
Explanation
Each shifts[i] shifts the first i+1 letters, so letter i actually gets pushed by the sum of all shifts at or after it. The smart move is to walk the string from right to left and keep a running suffix total, so every letter's true shift is ready in one pass.
We carry a variable total and at each step do total = (total + shifts[i]) % 26. Going right to left, total automatically accumulates every shift that affects position i. The % 26 keeps it small because the alphabet wraps every 26 letters.
To shift a letter we convert it to 0..25 with ord(s[i]) - ord('a'), add total, take % 26 to wrap around, and convert back to a character. This turns 'z' plus one into 'a' correctly.
Example: s = "abc", shifts = [3,5,9]. Suffix totals from the right are 9, then 14, then 17. So 'c'+9 = 'l', 'b'+14 = 'p', 'a'+17 = 'r', giving "rpl".
One sweep over the string makes this O(n), far better than re-shifting prefixes over and over.