Today’s problem

https://leetcode.com/problems/shifting-letters-ii/description/

Intuition

We need to write a datastructure to achieve a multi-range addition and a one-time query. Therefore, we can use difference Array and prefix sum.

Approach

In a difference array, we only count the difference of the edges of the change zone. For example, if we add the range $[l,r]$ by $k$, we only pay attention to point l and point r: we add the difference array $diff[l]$ by $k$, and then add the difference array $diff[r + 1]$ by $-k$. Now, if we calculate the prefix sum $s$ in range $[l,r]$, we find that the effect of addition $k$ will be added only in range $[l,r]$ in $s$. Therefore, by using the difference array and the prefix sum, we can deal with the one change in $O(1)$. Now, since we want to change the character, we can first change it into ASCII code, then subtract by the code of ‘a’. Then we can use a module of 26 to acheive the effect of “character rotation”.

Complexity

• Time complexity: $O(N + C)$, N is the length of the string, c is the number of changes.

• Space complexity: $O(N)$, we need to store the difference array.

Code

class Solution:
    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:
        dif = [0] * (len(s) + 1)
        for l,r,delta in shifts:
            if delta == 0:
                dif[l] -= 1
                dif[r + 1] += 1
            else:
                dif[l] += 1
                dif[r + 1] -= 1
        
        a = ord('a')
        cnt = 0
        ans = ""
        
        for i in range(len(s)):
            cnt += dif[i]
            ans += chr((ord(s[i]) - a + cnt) % 26 + a)

        return ans