Shifting Letters — LeetCode 848 Python Solution

The 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').

Example

Input

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

Output

"rpl"

Explanation

We start with "abc".

Python solution

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)

Complexity

Pattern: Prefix Sum

Precompute running totals once so any range query becomes a single subtraction. LeetCode 848. Shifting Letters is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Prefix Sum.

The prefix sum guide has the Python template for the pattern and the 157 LeetCode problems that use it.

Related problems