Approach #1: Prefix Sum [Accepted]

Intuition

Let's ask how many times the ith character is shifted.

Algorithm

The ith character is shifted shifts[i] + shifts[i+1] + ... + shifts[shifts.length - 1] times. That's because only operations at the ith operation and after, affect the ith character.

Let X be the number of times the current ith character is shifted. Then the next character i+1 is shifted X - shifts[i] times.

For example, if S.length = 4 and S[0] is shifted X = shifts[0] + shifts[1] + shifts[2] + shifts[3] times, then S[1] is shifted shifts[1] + shifts[2] + shifts[3] times, S[2] is shifted shifts[2] + shifts[3] times, and so on.

In general, we need to do X -= shifts[i] to maintain the correct value of X as we increment i.

Complexity Analysis

  • Time Complexity: , where is the length of S (and shifts).

  • Space Complexity: , the space needed to output the answer.


Analysis written by: @awice.