848. Shifting Letters

Actually this problem is not very easy for me.
bug1 -> I used a straightforward way to simulate the whole process at the very beginning and got TLE
Since the total number of shifts are accumulated, we can just scan from the last to the first shift and accumulate them
bug2 -> the sum overflows

Time O(#shifts)

Version #3 Prefix Sum
Extra O(n) Space
91.22 %
class Solution {
    public String shiftingLetters(String S, int[] shifts) {
        if (S ==  null || S.length() == 0 || shifts == null || shifts.length == 0) throw new IllegalArgumentException();
        shifts[shifts.length - 1] %= 26;
        for (int i = shifts.length - 2; i >= 0; i--) {
            shifts[i] = (shifts[i + 1] + shifts[i]) % 26;
        }
        char[] chars = S.toCharArray();
        for (int j = 0; j < S.length(); j++) {
            chars[j] = (char)('a' + (chars[j] - 'a' + shifts[j]) % 26);
        }
        return new String(chars);
    }
}

Version #2 sum % 26 -> better than using long

100.00 %
class Solution {
 public String shiftingLetters(String S, int[] shifts) {
if (S == null || S.length() == 0) {
return S;
}
char[] chars = S.toCharArray();
int sum = 0;
int i = shifts.length - 1;
while (i >= S.length()) {
sum += shifts[i];
i--;
}
for (; i >= 0; i--) {
sum = (sum + shifts[i]) % 26;
chars[i] = (char)('a' + (chars[i] - 'a' + sum) % 26);
}
return new String(chars);
}
}


Version #1 (long) sum

62.68 %
class Solution {
     public String shiftingLetters(String S, int[] shifts) {
if (S == null || S.length() == 0) {
return S;
}
char[] chars = S.toCharArray();
long sum = 0;
int i = shifts.length - 1;
while (i >= S.length()) {
sum += shifts[i];
i--;
}
for (; i >= 0; i--) {
sum += shifts[i];
chars[i] = (char)('a' + (chars[i] - 'a' + sum) % 26);
}
return new String(chars);
}
}