# Shifting Letters
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/shifting-letters)
Canonical: https://scaleengineer.com/dsa/problems/shifting-letters
**Patterns:** [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Data structures:** Array, String
---
## Problem
You are given a string `s` of lowercase English letters and an integer array `shifts` of the same length.

Call the `shift()` of a letter, the next letter in the alphabet, (wrapping around so that `'z'` becomes `'a'`).

* For example, `shift('a') = 'b'`, `shift('t') = 'u'`, and `shift('z') = 'a'`.

Now for each `shifts[i] = x`, we want to shift the first `i + 1` letters of `s`, `x` times.

Return _the final string after all such shifts to s are applied_.

**Example 1:**

**Input:** s = "abc", shifts = [3,5,9]
**Output:** "rpl"
**Explanation:** We start with "abc".
After shifting the first 1 letters of s by 3, we have "dbc".
After shifting the first 2 letters of s by 5, we have "igc".
After shifting the first 3 letters of s by 9, we have "rpl", the answer.

**Example 2:**

**Input:** s = "aaa", shifts = [1,2,3]
**Output:** "gfd"

**Constraints:**

* `1 <= s.length <= 105`
* `s` consists of lowercase English letters.
* `shifts.length == s.length`
* `0 <= shifts[i] <= 109`

# Approaches
## Brute Force Simulation
This approach directly simulates the process described in the problem. We iterate through each element of the `shifts` array and, for each `shifts[i]`, we update the first `i + 1` characters of the string. This involves nested loops, where the outer loop processes each shift operation and the inner loop applies that shift to the relevant prefix of the string.
**Time:** O(N^2), where N is the length of the string `s`. The outer loop runs N times, and the inner loop runs up to N times (for `i = N-1`, it runs N times). This results in a total of 1 + 2 + ... + N = N*(N+1)/2 operations, which is quadratic. · **Space:** O(N) to store the character array for the result. In Java, strings are immutable, so creating a character array or `StringBuilder` is necessary.
**Pros:** Simple to understand as it directly translates the problem statement into code.; Requires minimal algorithmic insight.
**Cons:** Highly inefficient due to the nested loops.; Will result in a 'Time Limit Exceeded' (TLE) error for the given constraints (N up to 10^5).
### Explanation
The algorithm works as follows:
1.  Convert the input string `s` into a mutable character array, let's call it `resultChars`, to allow for easy modification of individual characters.
2.  Iterate through the `shifts` array with an index `i` from `0` to `s.length() - 1`.
3.  For each `i`, we need to shift the first `i + 1` characters. So, we start another loop with an index `j` from `0` to `i`.
4.  Inside the inner loop, we calculate the new character for `resultChars[j]`. The shift amount is `shifts[i]`. The new character is found by:
    *   Getting the 0-indexed position of the character: `originalPos = resultChars[j] - 'a'`.
    *   Adding the shift amount and taking the result modulo 26 to handle wrapping around from 'z' to 'a': `newPos = (originalPos + shifts[i]) % 26`.
    *   Converting the new position back to a character: `resultChars[j] = (char)('a' + newPos)`.
5.  After the outer loop completes, all shifts have been applied. We convert the `resultChars` array back to a string and return it.

```java
class Solution {
    public String shiftingLetters(String s, int[] shifts) {
        char[] resultChars = s.toCharArray();
        int n = s.length();

        for (int i = 0; i < n; i++) {
            int shiftAmount = shifts[i];
            for (int j = 0; j <= i; j++) {
                int originalPos = resultChars[j] - 'a';
                // We need to handle large shift amounts, so we take modulo 26
                int newPos = (originalPos + shiftAmount) % 26;
                resultChars[j] = (char) ('a' + newPos);
            }
        }

        return new String(resultChars);
    }
}
```
### Algorithm
- Convert the input string `s` to a character array `resultChars`.
- Loop through the `shifts` array from `i = 0` to `n-1` (where `n` is the length of `s`).
- Inside this loop, start another loop from `j = 0` to `i`.
- For each character `resultChars[j]`, apply the shift `shifts[i]`.
- The shift operation is `(char_position + shift_amount) % 26`.
- After all loops complete, convert `resultChars` back to a string.

## Optimized Approach using Suffix Sum
A more efficient approach avoids re-calculating shifts for the same character multiple times. By observing the pattern of shifts, we can see that a character at index `i` is affected by all shifts from `shifts[i]` to `shifts[n-1]`. The total shift for `s[i]` is the sum of `shifts[i]`, `shifts[i+1]`, ..., `shifts[n-1]`. This is a classic suffix sum pattern. We can pre-calculate the total shift for each character in a single pass and then apply it.
**Time:** O(N), where N is the length of the string `s`. We iterate through the string and the shifts array only once from right to left. · **Space:** O(N) to store the character array for the result. This is necessary because strings are immutable in Java. The space for the `currentShift` variable is O(1).
**Pros:** Optimal linear time complexity, making it very efficient.; Processes the input in a single pass.; Handles large inputs within the time limits.
**Cons:** Slightly less intuitive than the brute-force approach as it requires identifying the suffix sum pattern.
### Explanation
The core idea is to determine the final, cumulative shift for each character before modifying the string.
Let `totalShift[i]` be the total amount character `s[i]` needs to be shifted.
- `s[n-1]` is only shifted by `shifts[n-1]`. So, `totalShift[n-1] = shifts[n-1]`.
- `s[n-2]` is shifted by `shifts[n-2]` and `shifts[n-1]`. So, `totalShift[n-2] = shifts[n-2] + shifts[n-1]`.
- In general, `totalShift[i] = shifts[i] + shifts[i+1] + ... + shifts[n-1]`.
This can be rewritten as `totalShift[i] = shifts[i] + totalShift[i+1]`.

This relationship allows us to compute all total shifts in a single pass, iterating from right to left.

The algorithm is as follows:
1.  Convert the input string `s` to a character array `resultChars`.
2.  Initialize a variable `currentShift` to 0. This will keep track of the cumulative shift from the right. Since the sum of shifts can exceed the capacity of a 32-bit integer, we should use a `long`.
3.  Iterate from the end of the string to the beginning (i.e., `i` from `n-1` down to `0`).
4.  In each iteration, update the `currentShift`: `currentShift = (currentShift + shifts[i]) % 26`. We take the modulo at each step to keep the number manageable.
5.  Now, `currentShift` holds the total shift amount for the character at index `i`. Apply this shift:
    *   `originalPos = resultChars[i] - 'a'`.
    *   `newPos = (originalPos + (int)currentShift) % 26`.
    *   `resultChars[i] = (char)('a' + newPos)`.
6.  After the loop, `resultChars` contains the final characters. Convert it back to a string.

This approach combines the calculation of suffix sums and the application of shifts into a single, efficient pass.

```java
class Solution {
    public String shiftingLetters(String s, int[] shifts) {
        char[] resultChars = s.toCharArray();
        int n = s.length();
        long currentShift = 0;

        // Iterate from right to left
        for (int i = n - 1; i >= 0; i--) {
            // Add the current shift and take modulo 26 to find the total shift for this position
            currentShift = (currentShift + shifts[i]) % 26;
            
            // Apply the total shift to the character
            int originalPos = resultChars[i] - 'a';
            int newPos = (originalPos + (int)currentShift) % 26;
            resultChars[i] = (char) ('a' + newPos);
        }

        return new String(resultChars);
    }
}
```
### Algorithm
- Convert the input string `s` to a character array `resultChars`.
- Initialize a `long` variable `currentShift` to 0.
- Iterate from the end of the string to the beginning (`i` from `n-1` down to `0`).
- Update the cumulative shift: `currentShift = (currentShift + shifts[i]) % 26`.
- Calculate the new character for `resultChars[i]` by applying `currentShift`.
- Update `resultChars[i]` with the new character.
- After the loop, convert `resultChars` back to a string and return it.

# Solutions
### Java

```java
class Solution { public String shiftingLetters ( String s , int [] shifts ) { char [] cs = s . toCharArray (); int n = cs . length ; long t = 0 ; for ( int i = n - 1 ; i >= 0 ; -- i ) { t += shifts [ i ]; int j = ( int ) (( cs [ i ] - 'a' + t ) % 26 ); cs [ i ] = ( char ) ( 'a' + j ); } return String . valueOf ( cs ); } }
```

### CPP

```cpp
class Solution { public: string shiftingLetters ( string s , vector < int >& shifts ) { long long t = 0 ; int n = s . size (); for ( int i = n - 1 ; ~ i ; -- i ) { t += shifts [ i ]; int j = ( s [ i ] - 'a' + t ) % 26 ; s [ i ] = 'a' + j ; } return s ; } };
```

### Python

```python
class Solution : def shiftingLetters ( self , s : str , shifts : List [ int ]) -> str : n , t = len ( s ), 0 s = list ( s ) for i in range ( n - 1 , - 1 , - 1 ): t += shifts [ i ] j = ( ord ( s [ i ]) - ord ( 'a' ) + t ) % 26 s [ i ] = ascii_lowercase [ j ] return '' . join ( s )
```