Rolling String
You are given a string $S$ of $n$ lowercase English letters and a list of $m$ range-roll operations. You must apply every operation in the given order and return the final string.
Each operation is a triple [i, j, dir] where $0 \le i \le j < n$ and dir is either 'R' (roll forward) or 'L' (roll backward): - A forward roll ('R') shifts every character at positions $i..j$ inclusive to the NEXT letter in the alphabet, with wraparound so 'z' becomes 'a'. - A backward roll ('L') shifts every character at positions $i..j$ inclusive to the PREVIOUS letter, with wraparound so 'a' becomes 'z'.
Applying all $m$ operations character-by-character is $O(n \cdot m)$, which is too slow at the limits. The intended solution records the net shift over each range with a difference array, prefix-sums it once, and then sets each output character to (S[c] - 'a' + shift[c]) mod 26.
Write a function rolling_string(s, ops) that takes the string s and the list of operations ops (each operation a 3-element list [i, j, dir]) and returns the final string.
Input contract: - s: a string of lowercase English letters, length $n$. - ops: a list of operations; each is [i, j, dir] with integers $0 \le i \le j < n$ and dir in {'R', 'L'}. -
ops list returns s unchanged).
Output contract: - Return the final string after all operations have been applied in order.
Worked example: s = "abz", ops = [[0, 2, "R"]]. The single forward roll shifts each of positions 0, 1, 2: a -> b, b -> c, z wraps to a. The result is "bca".
Hints
- Applying each roll directly is $O(n)$ per operation. Notice that a forward roll and a backward roll on the same position cancel, so only the NET shift per position matters.
- The net shift per position is the count of forward rolls minus backward rolls covering it. A range update of +1 (R) or -1 (L) on $i..j$ followed by a single query of every position is the classic difference-array pattern.
- For an operation on $i..j$ with sign
delta, dodiff[i] += deltaanddiff[j+1] -= delta(size the array $n+1$ soj+1is always valid). Prefix-sumdiffonce to recover the net shift at each position. - Map each output character with
(ord(s[c]) - ord('a') + cur) % 26. In Python the%operator returns a value in $0..25$ even whencuris negative, so 'a' rolling backward to 'z' works without a special case.
Worked Solution
Net shift is additive and order-independent: rolling a range forward then backward cancels, and a character's final letter depends only on the total signed number of times it was rolled, taken mod 26. So instead of touching each character on every operation, accumulate the net shift per position with a difference array.
Let diff be an array of length $n + 1$ initialized to zero. For each operation [i, j, dir], let delta = +1 for 'R' and delta = -1 for 'L', then do diff[i] += delta and diff[j + 1] -= delta. This marks the start and one-past-the-end of the affected range in $O(1)$.
After all operations, prefix-sum once: walk positions $c = 0..n-1$ keeping a running cur += diff[c]; cur is the net shift applied to position $c$. The output character is chr(ord('a') + (ord(s[c]) - ord('a') + cur) mod 26). Python's % already returns a non-negative result for a positive modulus even when cur is negative, so backward wraparound ('a' -> 'z') is handled automatically.
Total cost is $O(n + m)$: one $O(1)$ update per operation plus one linear pass over the string.
Intuition
Because the only thing that survives is each position's net (forward minus backward) roll count mod 26, you never have to replay the rolls. A difference array lets you stamp each range operation in $O(1)$ as a +1 at the start and a -1 just past the end, and a single prefix sum then reveals how many net rolls landed on every position. One modular shift per character finishes it, turning an $O(n \cdot m)$ brute force into a clean $O(n + m)$ pass.