1089MediumArrayStringPrefix Sum

Rolling Letters Over Stretches

Tracked in this browser only

Trains the technique from

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A tape of lowercase letters reads tape. Each entry rolls[i] = [from, to, forward] names a stretch of the tape from position from to position to, both ends included, and says which way every letter in that stretch rolls: 1 rolls each letter one step forward through the alphabet and 0 rolls it one step back.

The alphabet wraps round, so rolling 'z' forward gives 'a' and rolling 'a' back gives 'z'.

Apply every roll in the list and return the tape afterwards.

Examples

Example 1

Input: tape = "abc", rolls = [[0, 2, 1]]
Output: "bcd"

One roll forward over the whole tape moves each letter one step on.

Example 2

Input: tape = "az", rolls = [[0, 1, 1]]
Output: "ba"

Rolling both letters forward turns the a into b and wraps the z round to a.

Example 3

Input: tape = "abc", rolls = [[0, 0, 0]]
Output: "zbc"

Only the first letter is in the stretch, and rolling a backwards wraps it round to z.

Constraints

1 <= tape.length <= 5 * 10^4
1 <= rolls.length <= 5 * 10^4
rolls[i].length == 3
0 <= rolls[i][0] <= rolls[i][1] <= tape.length - 1
0 <= rolls[i][2] <= 1
The tape is made of lowercase English letters.

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def shifting_letters(tape: str, rolls: list[list[int]]) -> str:

Java

public String shiftingLetters(String tape, int[][] rolls)

The intended approach

Time O(n + m) for a tape of length n and m rolls.Space O(n) for the changes.

Applying each roll letter by letter would cost the rolls times the tape. But every roll adds the same amount to every position of a stretch, and the rolls only ever add up, so all that matters per position is the total amount rolled there. Record the rolls as changes rather than as totals. For a roll of one step forward over a stretch, add one at the stretch's start and take one away just past its end; for a roll backwards, do the same with minus one. Then one running total across the tape turns those changes into the amount rolled at every position, because a change entered at a start stays in the running total until the matching change just past the end cancels it. Finally roll each letter by its own amount, taken to a remainder against twenty-six so the wrap is handled, keeping the remainder non-negative so backward rolls behave.

Pythonentry point: shifting_letters

def shifting_letters(tape, rolls):
    n = len(tape)
    change = [0] * (n + 1)
    for roll in rolls:
        step = 1 if roll[2] == 1 else -1
        change[roll[0]] += step
        change[roll[1] + 1] -= step
    out = []
    running = 0
    for at in range(n):
        running += change[at]
        moved = (ord(tape[at]) - 97 + running) % 26
        out.append(chr(97 + moved))
    return "".join(out)

The obvious version

Apply the rolls one at a time, walking each stretch and rolling every letter in it there and then, wrapping round the alphabet as you go. Costs the rolls times the stretch lengths rather than one pass with recorded changes.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_shifting_letters(tape, rolls):
    marks = []
    for ch in tape:
        marks.append(ord(ch) - 97)
    for roll in rolls:
        step = 1 if roll[2] == 1 else -1
        for at in range(roll[0], roll[1] + 1):
            marks[at] = (marks[at] + step) % 26
    out = []
    for value in marks:
        out.append(chr(97 + value))
    return "".join(out)

How this problem was checked

Reference solution executed against 15 test cases — 15 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in