Problem
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.
Examples
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 * 104
shifts[i].length == 3
0 <= starti <= endi < s.length
0 <= directioni <= 1
s
consists of lowercase English letters.
Solution
Method 1 - Diffs with Prefix Sum
Here is the approach:
- Initialisation of the Difference Array:
- Create a difference array
diff
of the same length as the strings
and initialise it with zeroes. - For each shift operation, update the start and end indices of the
diff
array based on the direction (forward or backward shift).
- Create a difference array
- Applying the Shifts:
- Traverse through the
shifts
array. - If
directioni == 1
, increasediff[starti]
by 1 and decreasediff[endi + 1]
by 1. - If
directioni == 0
, decreasediff[starti]
by 1 and increasediff[endi + 1]
by 1.
- Traverse through the
- Creating the Final Shift Pattern:
- Convert the
diff
array into a cumulative sum array to get the net shift at each character index.
- Convert the
- *Applying the Shifts to the String:
- Traverse through the string
s
and apply the calculated shifts. Wrap around using modulo operation for alphabetic shifts.
- Traverse through the string
- Finalize the Result:
- Construct the final string from the updated characters.
Code
Java
class Solution {
public String shiftingLetters(String s, int[][] shifts) {
int n = s.length();
int[] diff = new int[n + 1];
for (int[] shift : shifts) {
int start = shift[0], end = shift[1], dir = shift[2];
if (dir == 1) {
diff[start]++;
if (end + 1 < n) diff[end + 1]--;
} else {
diff[start]--;
if (end + 1 < n) diff[end + 1]++;
}
}
int netShift = 0;
char[] ans = s.toCharArray();
for (int i = 0; i < n; i++) {
netShift += diff[i];
int shift = ((netShift % 26) + 26) % 26;
ans[i] = (char) ((ans[i] - 'a' + shift) % 26 + 'a');
}
return new String(ans);
}
}
Python
class Solution:
def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:
n: int = len(s)
diff: List[int] = [0] * (n + 1)
for start, end, direction in shifts:
if direction == 1:
diff[start] += 1
if end + 1 < n:
diff[end + 1] -= 1
else:
diff[start] -= 1
if end + 1 < n:
diff[end + 1] += 1
net_shift: int = 0
ans: List[str] = list(s)
for i in range(n):
net_shift += diff[i]
shift = (net_shift % 26 + 26) % 26
ans[i] = chr((ord(ans[i]) - ord('a') + shift) % 26 + ord('a'))
return ''.join(ans)
Complexity
- ⏰ Time complexity:
O(n + m)
wheren
is the length of the strings
andm
is the number of shifts. - 🧺 Space complexity:
O(n)
, mainly for the difference array.