Shifting Letters II — Difference Array

Problem

Given a string and shift operations (l, r, direction), apply all shifts and return the final string.

Approach — Difference Array

Build difference array. For forward shift +1 at l, -1 at r+1; backward is -1 at l, +1 at r+1. Prefix sum gives net shift at each position.

Time: O(n + q) | Space: O(n)

Solutions

Python

class Solution:
    def shiftingLetters(self, s: str, shifts: list[list[int]]) -> str:
        n=len(s); diff=[0]*(n+1)
        for l,r,d in shifts:
            v=1 if d==1 else -1
            diff[l]+=v; diff[r+1]-=v
        res=[]; shift=0
        for i,c in enumerate(s):
            shift=(shift+diff[i])%26
            res.append(chr((ord(c)-ord('a')+shift)%26+ord('a')))
        return ''.join(res)

Complexity

Time: O(n + q) | Space: O(n)