Problem Description

You are given a string s consisting of lowercase English letters, and an integer array shifts of the same length as s.
For each index i, you need to shift the first i + 1 letters of the string s by shifts[i] positions forward in the alphabet. Shifting a letter means replacing it with the letter that appears after it in the alphabet (wrapping around from 'z' to 'a' as necessary).

Return the final string after all the shifts have been applied.

Constraints:

• 1 <= s.length == shifts.length <= 10^5
• 0 <= shifts[i] <= 10^9
• Each character in s is a lowercase English letter.

• Each shifts[i] only applies to the first i + 1 letters.
• All shifts are summed cumulatively from right to left.
• There is exactly one valid output string.

Thought Process

At first glance, you might think to apply each shifts[i] to the first i+1 letters by looping through the string repeatedly. However, this would require a nested loop, resulting in an O(n²) solution, which is too slow for large inputs.

The key realization is that each character at position j gets shifted by all shifts[i] where i ≥ j. In other words, the total shift for each character is the sum of all shifts values from its index to the end of the array.

This means we should process the shifts array from right to left, keeping a running sum, and use that to shift each character only once.

Solution Approach

We solve the problem efficiently by following these steps:

• 1. Initialize a running sum:
  Start from the end of the shifts array and move leftwards, keeping track of the sum of all shifts seen so far.
• 2. For each character, compute its total shift:
  For character at index i, the total shift is the sum of shifts[i] and all values to its right. This can be done efficiently using the running sum.
• 3. Apply the shift to each character:
  For each character, convert it to a number (0 for 'a', 1 for 'b', ..., 25 for 'z'), add the running sum (modulo 26 for wrap-around), and convert it back to a character.
• 4. Build and return the final string:
  After processing all characters, join them into the result string.

Example Walkthrough

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

Let's trace the process:

• Start from the end: running_sum = 0
• i = 2: running_sum += 9 → running_sum = 9
  - Shift 'c' by 9: ('c' is 2, (2+9)%26 = 11) → 'l'
• i = 1: running_sum += 5 → running_sum = 14
  - Shift 'b' by 14: ('b' is 1, (1+14)%26 = 15) → 'p'
• i = 0: running_sum += 3 → running_sum = 17
  - Shift 'a' by 17: ('a' is 0, (0+17)%26 = 17) → 'r'

Code Implementation

class Solution:
    def shiftingLetters(self, s: str, shifts: List[int]) -> str:
        n = len(s)
        res = []
        total = 0
        for i in range(n-1, -1, -1):
            total = (total + shifts[i]) % 26
            shifted = (ord(s[i]) - ord('a') + total) % 26
            res.append(chr(shifted + ord('a')))
        return ''.join(res[::-1])
      

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

class Solution {
    public String shiftingLetters(String s, int[] shifts) {
        int n = s.length();
        int total = 0;
        char[] res = s.toCharArray();
        for (int i = n - 1; i >= 0; --i) {
            total = (total + shifts[i]) % 26;
            res[i] = (char) ((s.charAt(i) - 'a' + total) % 26 + 'a');
        }
        return new String(res);
    }
}
      

var shiftingLetters = function(s, shifts) {
    let n = s.length;
    let total = 0;
    let res = [];
    for (let i = n - 1; i >= 0; --i) {
        total = (total + shifts[i]) % 26;
        let shifted = (s.charCodeAt(i) - 97 + total) % 26;
        res[i] = String.fromCharCode(shifted + 97);
    }
    return res.join('');
};
      

Time and Space Complexity

Brute-force Approach:

• For each shifts[i], shift the first i+1 characters, resulting in O(n²) time.
• Not feasible for large input sizes.

• Single pass from right to left, O(n) time, where n is the length of s and shifts.
• Space: O(n) for the output string (or O(1) extra if modifying in-place).

Summary

The Shifting Letters problem is a classic case where a naive approach is too slow, but a simple cumulative sum trick leads to an efficient solution. By processing the shifts from right to left and keeping a running total, we shift each character the correct number of times in just one pass. This results in a clean, fast, and elegant solution suitable for large inputs.