In this guide, you will get 2381. Shifting Letters II LeetCode Solution with the best time and space complexity. The solution to Shifting Letters II problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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”.
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.
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(n)
2381. Shifting Letters II LeetCode Solution in C++
class Solution {
public:
string shiftingLetters(string s, vector<vector<int>>& shifts) {
int currShift = 0;
vector<int> timeline(s.length() + 1);
for (const vector<int>& shift : shifts) {
const int start = shift[0];
const int end = shift[1];
const int direction = shift[2];
const int diff = direction ? 1 : -1;
timeline[start] += diff;
timeline[end + 1] -= diff;
}
for (int i = 0; i < s.length(); ++i) {
currShift = (currShift + timeline[i]) % 26;
const int num = (s[i] - 'a' + currShift + 26) % 26;
s[i] = 'a' + num;
}
return s;
}
}; /* code provided by PROGIEZ */
2381. Shifting Letters II LeetCode Solution in Java
class Solution {
public String shiftingLetters(String s, int[][] shifts) {
StringBuilder sb = new StringBuilder();
int currShift = 0;
int[] timeline = new int[s.length() + 1];
for (int[] shift : shifts) {
final int start = shift[0];
final int end = shift[1];
final int direction = shift[2];
final int diff = direction == 1 ? 1 : -1;
timeline[start] += diff;
timeline[end + 1] -= diff;
}
for (int i = 0; i < s.length(); ++i) {
currShift = (currShift + timeline[i]) % 26;
final int num = (s.charAt(i) - 'a' + currShift + 26) % 26;
sb.append((char) ('a' + num));
}
return sb.toString();
}
} // code provided by PROGIEZ
2381. Shifting Letters II LeetCode Solution in Python
class Solution:
def shiftingLetters(self, s: str, shifts: list[list[int]]) -> str:
ans = []
currShift = 0
timeline = [0] * (len(s) + 1)
for start, end, direction in shifts:
diff = 1 if direction else -1
timeline[start] += diff
timeline[end + 1] -= diff
for i, c in enumerate(s):
currShift = (currShift + timeline[i]) % 26
num = (ord(c) - ord('a') + currShift + 26) % 26
ans.append(chr(ord('a') + num))
return ''.join(ans) # code by PROGIEZ
