Shifting Letters II

Medium · Arrays & Hashing · Explanation and code example

Binary Indexed Tree (Fenwick Tree)

How it works

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.

Steps

  1. Initialize a BIT of size n + 2.
  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.
  3. 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.
  4. Return the resulting string.

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.

Things to watch for

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.

Python code example

from typing import List

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)

C++ code example

class BIT {
    vector<int> tree;
    int n;
public:
    BIT(int size) {
        n = size + 2;
        tree.assign(n, 0);
    }

    void update(int index, int delta) {
        index++;
        while (index < n) {
            tree[index] += delta;
            index += index & -index;
        }
    }

    int prefixSum(int index) {
        index++;
        int sum = 0;
        while (index > 0) {
            sum += tree[index];
            index -= index & -index;
        }
        return sum;
    }

    void rangeUpdate(int left, int right, int delta) {
        update(left, delta);
        update(right + 1, -delta);
    }
};

class Solution {
public:
    string shiftingLetters(string s, vector<vector<int>>& shifts) {
        int n = s.size();
        BIT bit(n);

        for (auto& shift : shifts) {
            int left = shift[0], right = shift[1], d = shift[2];
            int delta = d == 1 ? 1 : -1;
            bit.rangeUpdate(left, right, delta);
        }

        string res;
        for (int i = 0; i < n; i++) {
            int shift = bit.prefixSum(i) % 26;
            int code = (s[i] - 'a' + shift + 26) % 26;
            res += char('a' + code);
        }

        return res;
    }
};
Source and license

Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.

Check the explanation on LeetCode

Your recall check is in progress. Write your attempt before revealing the explanation.

Resume recall check

Browse all problem explanations