2381. Shifting Letters II - Explanation

1. Brute Force

Intuition

The straightforward approach is to apply each shift operation directly. For each shift, we iterate through the specified range and increment or decrement each character. Since characters wrap around the alphabet, we use modulo 26 arithmetic.

This approach is simple but slow because we might repeatedly process the same characters across multiple overlapping shifts.

Algorithm

Convert the string to an array of integers (0-25 representing 'a'-'z').
For each shift [l, r, d]:
- Iterate through indices from l to r.
- Add 1 if direction is forward, subtract 1 if backward.
- Apply modulo 26 to handle wraparound.
Convert the integer array back to characters.
Return the resulting string.

class Solution:
    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:
        s = [ord(c) - ord('a') for c in s]

        for l, r, d in shifts:
            for i in range(l, r + 1):
                s[i] += 1 if d else -1
                s[i] %= 26

        s = [chr(ord('a') + c) for c in s]
        return "".join(s)

Time & Space Complexity

Time complexity: $O(n * m)$
Space complexity: $O(n)$

Where $n$ is the length of the string $s$ and $m$ is the size of the array $shifts$ .

2. Sweep Line Algorithm

Intuition

Instead of applying each shift individually, we can use a difference array technique. The idea is to mark where shifts begin and end, then compute the cumulative effect as we scan through the string.

For a shift affecting range [l, r], we add the shift value at index l and subtract it at index r + 1. When we compute the running sum (prefix sum) of this difference array, each position automatically accumulates the total shift from all overlapping operations.

Algorithm

Create a difference array prefix_diff of size n + 1, initialized to zeros.
For each shift [l, r, d]:
- Add +1 or -1 (based on direction) at index l.
- Subtract the same value at index r + 1.
Compute the running sum while traversing the string:
- Maintain a cumulative diff variable.
- For each index, add the net shift to the character.
- Apply modulo 26 arithmetic for wraparound.
Return the resulting string.

class Solution:
    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:
        prefix_diff = [0] * (len(s) + 1)

        for left, right, d in shifts:
            val = 1 if d == 1 else -1
            prefix_diff[left] += val
            prefix_diff[right + 1] -= val

        diff = 0
        res = [ord(c) - ord("a") for c in s]

        for i in range(len(s)):
            diff += prefix_diff[i]
            res[i] = (diff + res[i] + 26) % 26

        s = [chr(ord("a") + n) for n in res]
        return "".join(s)

Time & Space Complexity

Time complexity: $O(n + m)$
Space complexity: $O(n)$

Where $n$ is the length of the string $s$ and $m$ is the size of the array $shifts$ .

3. Binary Indexed Tree (Fenwick Tree)

Intuition

A Binary Indexed Tree (BIT) efficiently handles range updates and point queries. For this problem, we use the BIT to support range updates: when we need to add a value to all elements in range [l, r], we update at position l and cancel at position r + 1.

When querying, the prefix sum at any index gives us the total accumulated shift for that position. This is useful when shifts need to be applied dynamically or when we need to query intermediate results.

Algorithm

Initialize a BIT of size n + 2.
For each shift [l, r, d]:
- Perform a range update by calling update(l, delta) and update(r + 1, -delta), where delta is +1 or -1.
For each character in the string:
- Query the BIT to get the total shift at that position.
- Apply the shift with modulo 26 arithmetic.
- Build the result character.
Return the resulting string.

class BIT:
    def __init__(self, size):
        self.n = size + 2
        self.tree = [0] * self.n

    def update(self, index, delta):
        index += 1
        while index < self.n:
            self.tree[index] += delta
            index += index & -index

    def prefix_sum(self, index):
        index += 1
        total = 0
        while index > 0:
            total += self.tree[index]
            index -= index & -index
        return total

    def range_update(self, left, right, delta):
        self.update(left, delta)
        self.update(right + 1, -delta)


class Solution:
    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:
        n = len(s)
        bit = BIT(n)

        for left, right, d in shifts:
            delta = 1 if d == 1 else -1
            bit.range_update(left, right, delta)

        res = []
        for i in range(n):
            shift = bit.prefix_sum(i) % 26
            code = (ord(s[i]) - ord('a') + shift + 26) % 26
            res.append(chr(ord('a') + code))

        return ''.join(res)

Time & Space Complexity

Time complexity: $O((m + n) * \log n)$
Space complexity: $O(n)$

Where $n$ is the length of the string $s$ and $m$ is the size of the array $shifts$ .

Common Pitfalls

Forgetting to Handle Negative Modulo

When shifting characters backward, the intermediate result can become negative before applying modulo 26. In many programming languages, the modulo of a negative number returns a negative result (e.g., -1 % 26 = -1 in some languages). Always add 26 before taking the modulo to ensure the result is positive: ((shift + char) % 26 + 26) % 26.

Off-by-One Error in Difference Array

When using the sweep line or difference array technique, the cancellation must happen at index r + 1, not at r. Placing the cancellation at index r means the shift will not be applied to the last character in the range. Remember that prefix_diff[right + 1] -= val ensures the shift applies to all indices from left through right inclusive.

Overlooking Large Accumulated Shifts

With many overlapping shifts, the cumulative value can grow very large (positive or negative). Taking modulo only at the end of all accumulations is correct, but some implementations attempt to normalize after each shift, which can introduce subtle bugs. Ensure you handle the final modulo operation correctly after summing all prefix values.