2381: Shifting-Letters-II
Medium
table of contents
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 s, vector<vector<int>>& shifts) {
string shiftingLetters<int> ps (s.size()+1, 0);
vectorfor (vector<int> &shift : shifts) {
[shift[0]] += (shift[2] == 1 ? 1 : -1);
ps[shift[1]+1] += (shift[2] == 1 ? -1 : 1);
ps}
int counter = 0;
for (int i = 0; i < s.size(); ++i) {
+= ps[i];
counter [i] = (((s[i]-'a')+counter)%26 + 26)%26 + 'a';
s}
return s;
}
};