You are given a string s of lowercase English letters and a 2D integer array shifts where shifts[i] = [starti, endi, directioni]. For every i, shift the characters in s from the index starti to the index endi (inclusive) forward if directioni = 1, or shift the characters backward if directioni = 0.
Shifting a character forward means replacing it with the next letter in the alphabet (wrapping around so that 'z' becomes 'a'). Similarly, shifting a character backward means replacing it with the previous letter in the alphabet (wrapping around so that 'a' becomes 'z').
Return the final string after all such shifts to s are applied.
Example 1:
Input: s = "abc", shifts = [[0,1,0],[1,2,1],[0,2,1]] Output: "ace" Explanation: Firstly, shift the characters from index 0 to index 1 backward. Now s = "zac". Secondly, shift the characters from index 1 to index 2 forward. Now s = "zbd". Finally, shift the characters from index 0 to index 2 forward. Now s = "ace".
Example 2:
Input: s = "dztz", shifts = [[0,0,0],[1,1,1]] Output: "catz" Explanation: Firstly, shift the characters from index 0 to index 0 backward. Now s = "cztz". Finally, shift the characters from index 1 to index 1 forward. Now s = "catz".
Constraints:
1 <= s.length, shifts.length <= 5 * 104shifts[i].length == 30 <= starti <= endi < s.length0 <= directioni <= 1sconsists of lowercase English letters.
class Solution:
def shiftingLetters(self, s: str, shifts: list[list[int]]) -> str:
n = len(s)
shift = [0] * (n + 1)
for shiftOp in shifts:
start, end, direction = shiftOp
shift[start] += (1 if direction == 1 else -1)
if end + 1 < n:
shift[end + 1] -= (1 if direction == 1 else -1)
currentShift = 0
shiftList = list(s)
for i in range(n):
currentShift += shift[i]
netShift = (currentShift % 26 + 26) % 26
shiftList[i] = chr((ord(shiftList[i]) - ord('a') + netShift) % 26 + ord('a'))
return ''.join(shiftList)
Example Walkthrough
Example 1:
Input: s = "abc", shifts = [[0,1,0],[1,2,1],[0,2,1]]
- Initial
delta:[0, 0, 0, 0](1 extra slot for boundary adjustment). - Processing shifts:
- [0,1,0][0,1,0]: delta=[−1,0,1,0]delta = [-1, 0, 1, 0]
- [1,2,1][1,2,1]: delta=[−1,1,0,−1]delta = [-1, 1, 0, -1]
- [0,2,1][0,2,1]: delta=[0,1,0,−2]delta = [0, 1, 0, -2]
- Prefix Sum:
- shift=[0,1,1,−1]shift = [0, 1, 1, -1]
- Shifting Characters:
'a' -> 'a''b' -> 'c''c' -> 'e'
- Result:
"ace"
Example 2:
Input: s = "dztz", shifts = [[0,0,0],[1,1,1]]
- Initial
delta:[0, 0, 0, 0, 0]. - Processing shifts:
- [0,0,0][0,0,0]: delta=[−1,1,0,0,0]delta = [-1, 1, 0, 0, 0]
- [1,1,1][1,1,1]: delta=[−1,0,1,0,0]delta = [-1, 0, 1, 0, 0]
- Prefix Sum:
- shift=[−1,−1,0,0]shift = [-1, -1, 0, 0]
- Shifting Characters:
'd' -> 'c''z' -> 'a''t' -> 't''z' -> 'z'
- Result:
"catz"
Unique Length-3 Palindromic Subsequences