LeetCode 848: Shifting Letters

Problem Restatement

We are given a lowercase string s and an integer array shifts of the same length.

A shift moves a character to the next letter in the alphabet, wrapping around from "z" to "a".

For each shifts[i] = x, we shift the first i + 1 letters of s by x positions.

Return the final string after all shifts are applied.

Input and Output

Function shape:

class Solution:
    def shiftingLetters(self, s: str, shifts: list[int]) -> str:
        ...

Examples

Example 1:

s = "abc"
shifts = [3, 5, 9]

Apply each operation:

"abc" -> "dbc"
"dbc" -> "igc"
"igc" -> "rpl"

So the answer is:

"rpl"

Example 2:

s = "aaa"
shifts = [1, 2, 3]

Character s[0] is shifted by:

1 + 2 + 3 = 6

Character s[1] is shifted by:

2 + 3 = 5

Character s[2] is shifted by:

3

So:

"a" -> "g"
"a" -> "f"
"a" -> "d"

The answer is:

"gfd"

First Thought: Simulate Every Operation

A direct solution is to apply every shift operation one by one.

For operation i, shift characters from index 0 through index i.

class Solution:
    def shiftingLetters(self, s: str, shifts: list[int]) -> str:
        chars = list(s)

        for i, amount in enumerate(shifts):
            for j in range(i + 1):
                old = ord(chars[j]) - ord("a")
                new = (old + amount) % 26
                chars[j] = chr(new + ord("a"))

        return "".join(chars)

This gives the correct result, but it repeats too much work.

Problem With Brute Force

There are n operations.

Operation i touches i + 1 characters.

The total work is:

1 + 2 + 3 + ... + n

which is:

O(n^2)

Since s.length can be up to 10^5, this is too slow.

Key Insight

A character at index j is affected by every operation whose index i satisfies:

i >= j

So the total shift for s[j] is:

shifts[j] + shifts[j + 1] + ... + shifts[n - 1]

That is a suffix sum.

Instead of applying operations forward, compute the running suffix sum from right to left.

Algorithm

1. Convert s into a list of characters.
2. Set total_shift = 0.
3. Scan from right to left.
4. Add shifts[i] to total_shift.
5. Reduce total_shift modulo 26.
6. Shift s[i] by total_shift.
7. Return the joined string.

Modulo 26 is enough because shifting by 26 returns the same letter.

Walkthrough

Use:

s = "abc"
shifts = [3, 5, 9]

Scan from right to left.

At index 2:

total_shift = 9
"c" + 9 = "l"

At index 1:

total_shift = 9 + 5 = 14
"b" + 14 = "p"

At index 0:

total_shift = 14 + 3 = 17
"a" + 17 = "r"

Final string:

"rpl"

Correctness

For each index j, the character s[j] is shifted by operation j, operation j + 1, and every later operation, because each of those operations shifts the first i + 1 characters and therefore includes index j.

No operation with index smaller than j affects s[j], because it only shifts positions up to that smaller index.

Therefore, the required total shift for s[j] is exactly the suffix sum:

shifts[j] + shifts[j + 1] + ... + shifts[n - 1]

The algorithm scans from right to left and maintains exactly this suffix sum in total_shift.

At each index, it shifts the character by that exact amount modulo 26. Modulo 26 preserves the final letter because the alphabet has 26 letters.

Thus every character is transformed exactly as required, so the returned string is correct.

Complexity

The extra space is for the output list. Apart from the output, the algorithm uses constant space.

Implementation

class Solution:
    def shiftingLetters(self, s: str, shifts: list[int]) -> str:
        chars = list(s)
        total_shift = 0

        for i in range(len(s) - 1, -1, -1):
            total_shift = (total_shift + shifts[i]) % 26

            original = ord(chars[i]) - ord("a")
            shifted = (original + total_shift) % 26

            chars[i] = chr(shifted + ord("a"))

        return "".join(chars)

Code Explanation

We convert the string to a list because strings are immutable:

chars = list(s)

The running suffix sum starts at zero:

total_shift = 0

Scan from the last index to the first:

for i in range(len(s) - 1, -1, -1):

Add the current shift:

total_shift = (total_shift + shifts[i]) % 26

The modulo keeps the number small.

Convert the character to a number from 0 to 25:

original = ord(chars[i]) - ord("a")

Apply the shift:

shifted = (original + total_shift) % 26

Convert it back to a character:

chars[i] = chr(shifted + ord("a"))

Finally, join the list:

return "".join(chars)

Testing

def run_tests():
    s = Solution()

    assert s.shiftingLetters("abc", [3, 5, 9]) == "rpl"
    assert s.shiftingLetters("aaa", [1, 2, 3]) == "gfd"
    assert s.shiftingLetters("z", [1]) == "a"
    assert s.shiftingLetters("abc", [26, 26, 26]) == "abc"
    assert s.shiftingLetters("xyz", [1, 1, 1]) == "zab"

    print("all tests passed")

run_tests()

Test meaning: