2381: Shifting-Letters-II
Medium

The trick to this question also lies within the prefix sum.

In my algorithm, instead of brute-forcing and incrementing every letter in s between start and end for each shift operation, you create another array, ps, such that you keep track of each shift operation by only incrementing/decrementing the start and end index in ps.

The thought-process is that since we are iterating through the array regardless, it would be most efficient to simulatenously calculate and shift s[i]. We can do this using a global counter variable to keep track of each character’s shift amount when we iterate past them.

This is because, for example, if we want to increment all the characters between index 5 and 10, we can simply increment counter at index 5 and decrement counter at index 11 (so that s[i]+counter gets incremented for indexes 5 to 10). We can do this for each shift operation and track this using the ps array.

Code:

class Solution {
public:
    string shiftingLetters(string s, vector<vector<int>>& shifts) {
        vector<int> ps (s.size()+1, 0);
        for (vector<int> &shift : shifts) {
            ps[shift[0]] += (shift[2] == 1 ? 1 : -1);
            ps[shift[1]+1] += (shift[2] == 1 ? -1 : 1);
        }
        
        int counter = 0;
        for (int i = 0; i < s.size(); ++i) {
            counter += ps[i];
            s[i] = (((s[i]-'a')+counter)%26 + 26)%26 + 'a';
        }
        return s;
    }
};

Complexity: