# 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

| Item | Meaning |
|---|---|
| Input | String `s` and array `shifts` |
| Output | Final shifted string |
| Shift rule | `"a" -> "b"`, `"b" -> "c"`, ..., `"z" -> "a"` |
| Operation `i` | Shift first `i + 1` characters by `shifts[i]` |
| Wraparound | Use modulo `26` |

Function shape:

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

## Examples

Example 1:

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

Apply each operation:

```python
"abc" -> "dbc"
"dbc" -> "igc"
"igc" -> "rpl"
```

So the answer is:

```python
"rpl"
```

Example 2:

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

Character `s[0]` is shifted by:

```python
1 + 2 + 3 = 6
```

Character `s[1]` is shifted by:

```python
2 + 3 = 5
```

Character `s[2]` is shifted by:

```python
3
```

So:

```python
"a" -> "g"
"a" -> "f"
"a" -> "d"
```

The answer is:

```python
"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`.

```python
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:

```python
1 + 2 + 3 + ... + n
```

which is:

```python
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:

```python
i >= j
```

So the total shift for `s[j]` is:

```python
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:

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

Scan from right to left.

At index `2`:

```python
total_shift = 9
"c" + 9 = "l"
```

At index `1`:

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

At index `0`:

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

Final string:

```python
"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:

```python
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

| Metric | Value | Why |
|---|---:|---|
| Time | `O(n)` | One right-to-left scan |
| Space | `O(n)` | Store output characters |

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

## Implementation

```python
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:

```python
chars = list(s)
```

The running suffix sum starts at zero:

```python
total_shift = 0
```

Scan from the last index to the first:

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

Add the current shift:

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

The modulo keeps the number small.

Convert the character to a number from `0` to `25`:

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

Apply the shift:

```python
shifted = (original + total_shift) % 26
```

Convert it back to a character:

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

Finally, join the list:

```python
return "".join(chars)
```

## Testing

```python
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:

| Test | Why |
|---|---|
| `"abc"` | Standard example |
| `"aaa"` | Confirms suffix sums differ by index |
| `"z"` | Confirms wraparound |
| Shifts of `26` | Confirms modulo behavior |
| `"xyz"` | Confirms multiple wraparounds |