Shifting Letters II - Video Solutions

Problem Overview: You receive a lowercase string s and several shift operations. Each operation specifies a range [l, r] and a direction. All characters in that range shift forward or backward in the alphabet. After applying every operation, return the final string.

Approach 1: Direct Simulation (O(n * m) time, O(1) space)

The most straightforward method applies each shift operation directly to the affected substring. For every query, iterate from l to r and update each character by shifting it forward or backward using modular arithmetic ((c - 'a' ± 1) % 26). This mirrors the problem statement and is easy to implement. The drawback is performance: if the string length is n and there are m operations, each potentially touching up to n characters, the worst‑case runtime becomes O(n * m). This works for small inputs but quickly becomes too slow when both the string and the number of operations are large. It mainly helps verify correctness before optimizing.

Approach 2: Prefix Sum Array (O(n + m) time, O(n) space)

A more efficient solution treats shifts like range updates. Instead of updating every character immediately, record the effect of each operation using a difference array. For a forward shift on [l, r], add +1 at index l and -1 at r + 1. For a backward shift, apply -1 and +1. After processing all operations, compute a running prefix sum to determine the total shift affecting each position. Then apply the final shift to each character using modulo 26. This converts repeated range updates into constant‑time operations and processes the string only once. The technique is a classic use of a prefix sum difference array and works especially well for problems involving many range modifications.

During the final pass, convert each character to its numeric position, apply the accumulated shift (handling negative values with modulo), and map it back to a letter. The algorithm touches each query once and each character once, giving O(n + m) time complexity and O(n) extra space.

Recommended for interviews: The prefix sum approach is what interviewers expect. It demonstrates recognition of range‑update patterns and efficient use of arrays. The brute-force simulation shows you understand the problem mechanics, but the optimized solution proves you can reduce repeated work using prefix accumulation techniques often seen in string and array manipulation problems.