848. Shifting Letters

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.

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 <= 10⁵
s consists of lowercase English letters.
shifts.length == s.length
0 <= shifts[i] <= 10⁹

Solutions

Solution 1: Suffix Sum

For each character in the string \(s\), we need to calculate its final shift amount, which is the sum of \(\textit{shifts}[i]\), \(\textit{shifts}[i + 1]\), \(\textit{shifts}[i + 2]\), and so on. We can use the concept of suffix sum, traversing \(\textit{shifts}\) from back to front, calculating the final shift amount for each character, and then taking modulo \(26\) to get the final character.

The time complexity is \(O(n)\), where \(n\) is the length of the string \(s\). Ignoring the space consumption of the answer, the space complexity is \(O(1)\).

Python3JavaC++Go

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)

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);
    }
}

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;
    }
};

func shiftingLetters(s string, shifts []int) string {
    t := 0
    n := len(s)
    cs := []byte(s)
    for i := n - 1; i >= 0; i-- {
        t += shifts[i]
        j := (int(cs[i]-'a') + t) % 26
        cs[i] = byte('a' + j)
    }
    return string(cs)
}

848. Shifting Letters

Description

Solutions

Solution 1: Suffix Sum

Comments