Domain 2MediumMEDIUM

Shifting Letters

Accumulate suffix sums of shifts and apply cumulative modulo wrap-around to each character in a single backward pass.

Domain: medium•Updated: 2026-09-02
#suffix sum#string manipulation#O(N)#modular arithmetic

Problem Breakdown

We are given a string S consisting of lowercase English letters and an integer array shifts. The operation is defined as follows: for every index i, we apply the shift value shifts[i] to all characters in the prefix S[0...i]. This means character at index 0 gets shifted by every element in shifts, while a character at index k only gets shifted by elements from shifts[k] onwards.

Inputs:

  • String S: Lowercase letters, length NN.
  • Integer array shifts: Length equal to len(S). Values can be large (10910^9).

Outputs:

  • Modified string after applying all shifts with wrap-around (‘z’ -> ‘a’).

Constraints & Edge Cases:

  • Length: Up to 20,000. This rules out O(N2)O(N^2) solutions where we simulate each shift on the prefix repeatedly.
  • Shift Values: Can be very large (10910^9). We must use modulo arithmetic (modulo 26) rather than simulating individual character steps for every unit of shift to avoid performance issues and unnecessary computation, though Python handles large integers automatically.
  • Wrap-around: The alphabet is cyclic (‘z’ + 1 = ‘a’).

Intuition

A naive approach would be to iterate through shifts from left to right. For each index i, we update the substring S[0...i]. Since updating a prefix of length kk takes O(k)O(k) time, doing this for all NN indices results in an overall complexity of ∑i=1Ni=O(N2)\sum_{i=1}^{N} i = O(N^2). Given N≤20,000N \le 20,000, N2N^2 is roughly 4×1084 \times 10^8 operations, which will likely time out.

Key Insight: Notice that the character at index k in string S participates in every shift operation where the prefix length covers it. Specifically, when we process shifts[i], all characters from index 0 to i are shifted by shifts[i]. Therefore, a character at index k is affected by every shifts[j] where j≥kj \ge k. This implies that the total shift applied to S[k] is simply the sum of all elements in shifts from index k to the end. We can compute this efficiently using a suffix-sum approach (or iterating backwards).

Approach

  1. Convert string S into a mutable list of characters, as strings are immutable in Python.
  2. Initialize a variable current_shift_total = 0. This will track the cumulative shifts for the current character we are processing.
  3. Iterate through the array shifts and string indices from right to left (from N−1N-1 down to 00).
  4. At each index i, add shifts[i] to current_shift_total.
  5. Apply this total shift to character S[i]:
    • Calculate the new ASCII value: (ord(S[i]) + current_shift_total) % 26.
    • Add back offset for ‘a’ (97) and update the list element.
  6. Join the modified list into a string and return it.

Complexity Analysis

  • Time Complexity: O(N)O(N), where NN is the length of S. We perform a single pass over the array to compute suffix sums and apply shifts. All arithmetic operations are constant time (Python handles large integers efficiently).
  • Space Complexity: O(1)O(1) auxiliary space if we consider the input/output storage separate from our logic variables, or strictly speaking O(N)O(N) because we need an extra list of characters to build the result string in Python due to immutability. In interview contexts, this is often cited as O(1)O(1) auxiliary beyond output requirements.

Solution

from typing import List

class Solution:
    def shiftingLetters(self, S: str, shifts: List[int]) -> str:
        # Convert immutable string to a list of characters for mutability
        s_list = list(S)
        
        current_shift_total = 0
        
        # Iterate backwards from the last character to the first.
        # This allows us to accumulate the total shift needed for each position 
        # in one pass (suffix sum logic).
        for i in range(len(shifts) - 1, -1, -1):
            current_shift_total += shifts[i]
            
            # Apply modulo arithmetic:
            # ord(c) gives ASCII value. We normalize to 'a'-'z', add shift, 
            # take mod 26 for wrap-around, then convert back to char code.
            s_list[i] = chr((ord(s_list[i]) - ord('a') + current_shift_total) % 26 + ord('a'))
            
        return "".join(s_list)

Edge Cases Handled

  • Large Shift Values: Since shifts can be up to 10910^9, we rely on Python’s arbitrary precision integers and the modulo operator %. This ensures that shifting ‘z’ by a billion times correctly wraps around multiple cycles without overflow errors (common in languages like C++ or Java).
  • Zero Shifts: If shifts[i] is 0, it adds nothing to the accumulator. The character remains unchanged relative to its current state before this step’s accumulation logic applies.
  • Single Character String: Loop runs once for index 0; accumulates total shift and updates correctly.