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 . - Integer array
shifts: Length equal tolen(S). Values can be large ().
Outputs:
- Modified string after applying all shifts with wrap-around (‘z’ -> ‘a’).
Constraints & Edge Cases:
- Length: Up to 20,000. This rules out solutions where we simulate each shift on the prefix repeatedly.
- Shift Values: Can be very large (). 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 takes time, doing this for all indices results in an overall complexity of . Given , is roughly 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 .
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
- Convert string
Sinto a mutable list of characters, as strings are immutable in Python. - Initialize a variable
current_shift_total = 0. This will track the cumulative shifts for the current character we are processing. - Iterate through the array
shiftsand string indices from right to left (from down to ). - At each index
i, addshifts[i]tocurrent_shift_total. - 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.
- Calculate the new ASCII value:
- Join the modified list into a string and return it.
Complexity Analysis
- Time Complexity: , where 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: auxiliary space if we consider the input/output storage separate from our logic variables, or strictly speaking 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 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
shiftscan be up to , 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.