Shifting Letters - Leetcode Solution

The Shifting Letters problem on LeetCode asks us to shift each letter in a given string s by some integer value K. The value of K for each letter is determined by an array of integers shifts.

The problem can be solved using the following algorithm:

1. Compute the total shift for each position in the string s.
2. For each position i in the string s, compute the new character by adding the total shift for that position to the ASCII value of the original character.
3. Handle the case where the new character exceeds the ASCII value of 'z' by taking the modulo with 26 (the number of letters in the English alphabet).
4. Convert the ASCII value of the new character back to a letter and append it to the output string.

Here is the Python code implementation of the above algorithm:

def shiftingLetters(s: str, shifts: List[int]) -> str:
    n = len(s)
    total_shift = [0] * n
    total_shift[n-1] = shifts[n-1]
    
    # compute the total shift for each character
    for i in range(n-2, -1, -1):
        total_shift[i] = total_shift[i+1] + shifts[i]
    
    # compute the new string by shifting each character
    new_str = ""
    for i in range(n):
        new_chr = ord(s[i]) + total_shift[i]
        if new_chr > ord('z'):
            new_chr = (new_chr - ord('z') - 1) % 26 + ord('a')
        new_str += chr(new_chr)
    
    return new_str

The time complexity of this algorithm is O(n), where n is the length of the string s. This is because we iterate over the string s and the shifts array only once. The space complexity is also O(n), since we use an additional array of size n to store the total shift for each position in the string.

1class Solution {
2public:
3    string shiftingLetters(string S, vector<int>& shifts) {
4        // Your code here
5        for (int i = shifts.size() - 2; i >= 0; i--) {
6            shifts[i] += shifts[i + 1];
7        }
8        for (int i = 0; i < S.size(); i++) {
9            S[i] = (S[i] - 'a' + shifts[i]) % 26 + 'a';
10        }
11        return S;
12    }
13};