Problem Statement
Brute Force [TLE]
class Solution:
def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:
arr = list(s)
for start, end, direction in shifts:
for i in range(start, end + 1):
c = arr[i]
if direction == 0:
direction = -1
val = (ord(c) - ord('a') + direction) % 26 + ord('a')
arr[i] = chr(val)
return ''.join(arr)
class Solution:
def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:
arr = list(s)
prefix = [0] * len(s)
for start, end, direction in shifts:
for i in range(start, end + 1):
prefix[i] += -1 if direction == 0 else 1
for i in range(len(s)):
c = s[i]
arr[i] = chr((ord(c) - ord('a') + prefix[i]) % 26 + ord('a'))
return ''.join(arr)
Editorial
Approach: Difference Array
class Solution:
def shiftingLetters(self, s: str, shifts: list[list[int]]) -> str:
n = len(s)
diff_array = [
0
] * n # Initialize a difference array with all elements set to 0
# Process each shift operation
for shift in shifts:
if shift[2] == 1: # If direction is forward (1)
diff_array[shift[0]] += 1 # Increment at the start index
if shift[1] + 1 < n:
diff_array[
shift[1] + 1
] -= 1 # Decrement at the end+1 index
else: # If direction is backward (0)
diff_array[shift[0]] -= 1 # Decrement at the start index
if shift[1] + 1 < n:
diff_array[
shift[1] + 1
] += 1 # Increment at the end+1 index
result = list(s)
number_of_shifts = 0
# Apply the shifts to the string
for i in range(n):
number_of_shifts = (
number_of_shifts + diff_array[i]
) % 26 # Update cumulative shifts, keeping within the alphabet range
if number_of_shifts < 0:
number_of_shifts += 26 # Ensure non-negative shifts
# Calculate the new character by shifting `s[i]`
shifted_char = chr(
(ord(s[i]) - ord("a") + number_of_shifts) % 26 + ord("a")
)
result[i] = shifted_char
return "".join(result)
