My first approach to the problem was to directly apply each shift operation to the string. Then I remembered the shege I've seen in the hand of TLE but here is my first thought. First, I convert the input string s into a list and also store the entire English alphabet as a string ("abcdefghijklmnopqrstuvwxyz") so I can easily reference the positions of each character during the shifts.
Next, I iterate through the shifts array, where each shift operation consists of three values: start, end, and direction. The start and end values define the range of indices in the string that I need to modify, and direction tells me whether to shift the characters forward (1) or backward (0).
For each shift, I loop through the range of indices specified by start and end. For every character in this range, I calculate its new position in the alphabet based on the shift direction. If the direction is forward (1), I move the character one step forward in the alphabet, wrapping around to 'a' if the character is 'z'. If the direction is backward (0), I move the character one step backward, wrapping around to 'z' if the character is 'a'. To do this, I use the alphabet.index() function to find the current position of the character in the alphabet, and I apply modular arithmetic to calculate the new position.
Once all the shifts are completed, I join the modified list of characters back into a single string using "".join(s) and return it as the final result. This solution is simple and straightforward, but I realize it can be inefficient for large inputs because I repeatedly search for character indices in the alphabet and modify characters in nested loops. The time complexity of this approach is O(m * n), where (m) is the number of shift operations and (n) is the average size of the ranges being shifted. While it works for smaller cases, I would consider optimizing this solution for better performance on larger inputs.
Why not use prefix sums?
First, I initialize an array called shift_delta with a size of (n+1) where (n) is the length of the string. This array will help me keep track of the cumulative effect of all shifts in a range using a difference array technique.
Next, I iterate through the shifts array. For each shift, I determine whether the direction is forward (1) or backward (0) and assign a shift amount of +1 or -1 accordingly. I update the shift_delta array by adding the shift_amount to the start index and subtracting it from the end + 1 index (if it is within bounds).
After processing all the shifts, I compute the prefix sum of the shift_delta array to determine the net shift at each position in the string. I also convert the input string s into a list to allow mutability during this process. As I iterate through the string, I add the current value of shift_delta to a running total (current_shift) and use it to calculate the new character for each position.
To determine the new character, I use modular arithmetic. I calculate the shift relative to the ASCII value of 'a', adjust it using the current_shift, and take the result modulo 26 to ensure it wraps around correctly for the alphabet. Finally, I convert the adjusted value back into a character and update the string. Once all characters have been updated, I join the list back into a string and return the final result.
class Solution:
def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:
n = len(s)
shift_delta = [0] * (n + 1)
for start, end, direction in shifts:
shift_amount = 1 if direction == 1 else -1
shift_delta[start] += shift_amount
if end + 1 < n:
shift_delta[end + 1] -= shift_amount
current_shift = 0
s = list(s)
for i in range(n):
current_shift += shift_delta[i]
new_char = (ord(s[i]) - ord('a') + current_shift) % 26
s[i] = chr(ord('a') + new_char)
return "".join(s)- Time: O(m+n) where m is the number of shifts and n is the length of the string.
- Space: O(n) for
shift_delta.
