848. Shifting Letters

Problem Description

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.

Examples:

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.

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

Constraints:

• 1 ≤ s.length ≤ 10⁵
• s consists of lowercase English letters
• shifts.length == s.length
• 0 ≤ shifts[i] ≤ 10⁹

Python Solution

class Solution:
    def shiftingLetters(self, s: str, shifts: List[int]) -> str:
        # Calculate cumulative shifts from right to left
        n = len(s)
        total_shift = 0
        result = [''] * n
        
        for i in range(n - 1, -1, -1):
            total_shift = (total_shift + shifts[i]) % 26
            # Convert character to 0-25 range, add shift, convert back to char
            curr_char = ord(s[i]) - ord('a')
            new_char = (curr_char + total_shift) % 26
            result[i] = chr(new_char + ord('a'))
        
        return ''.join(result)

Implementation Notes:

• Uses cumulative sum from right to left to handle shifts efficiently
• Time complexity: O(n)
• Space complexity: O(n)

Java Solution

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

C++ Solution

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

JavaScript Solution

/**
 * @param {string} s
 * @param {number[]} shifts
 * @return {string}
 */
var shiftingLetters = function(s, shifts) {
    const n = s.length;
    const result = new Array(n);
    let totalShift = 0;
    
    for (let i = n - 1; i >= 0; i--) {
        totalShift = (totalShift + shifts[i]) % 26;
        const charCode = s.charCodeAt(i) - 97;
        result[i] = String.fromCharCode(((charCode + totalShift) % 26) + 97);
    }
    
    return result.join('');
};

C# Solution

public class Solution {
    public string ShiftingLetters(string s, int[] shifts) {
        int n = s.Length;
        char[] result = s.ToCharArray();
        long totalShift = 0;
        
        for (int i = n - 1; i >= 0; i--) {
            totalShift = (totalShift + shifts[i]) % 26;
            result[i] = (char)((s[i] - 'a' + totalShift) % 26 + 'a');
        }
        
        return new string(result);
    }
}

Implementation Notes:

• Uses long to handle large cumulative shifts
• Time complexity: O(n)
• Space complexity: O(n)