Pretty straightforward approach. Consider an example, S = “abc” and shifts = [3,5,9]. In total, the first letter has to be shifted shifts[0]+shifts[1]+shifts[2] times. The second letter has to be shifted shifts[1]+shifts[2] times and the third letter has to be shifted shifts[2] times.
It is clear that S[i] has to be shifted S[i]+S[i+1]+…+S[n-1] times. This is essentially the suffix sum of the shifts array.
Another thing to note is that a shift by 2 is equivalent to a shift by 28 as there are only 26 English alphabets. So a shift by 26 is equivalent to not shifting at all. So to prevent overflow in our suffix sum calculation, we will do %26 (MOD 26) at each step.
class Solution {
public:
string shiftingLetters(string S, vector<int>& shifts) {
int sum = 0;
for (int i=shifts.size()-1; i>=0; i--) {
sum=(sum+shifts[i])%26;
shifts[i] = sum;
}
string res = "";
for (int i=0; i<shifts.size(); i++) {
int k = S[i]-'a';
k = (k+shifts[i])%26;
res += k+'a';
}
return res;
}
};
Time complexity: O(n)
Space complexity: O(1) // O(n) is you create a difference suffix array
We actually do not even need to store the suffix. We can just change create our string on-the-go and then reverse it (or you can change the input string directly):
class Solution {
public:
string shiftingLetters(string S, vector<int>& shifts) {
int sum = 0;
string res = "";
for (int i=shifts.size()-1; i>=0; i--) {
sum=(sum+shifts[i])%26;
res+=(S[i]-'a'+sum)%26+'a';
}
reverse(res.begin(), res.end());
return res;
}
};
Time complexity: O(n) Space complexity: O(1) // without considering the string to be returned