2381. Shifting Letters II
Problem Description
You are provided with a string s
composed of lowercase English letters, and a list of shift operations represented by a 2D integer array shifts
. Each shift operation is described by a triplet [start, end, direction]
, and you are tasked with performing each of these operations on s
.
When you perform a shift operation, you will be shifting every character in the string s
starting at index start
up to and including index end
. If direction
is 1
, each character will be shifted forward in the alphabet (cyclically, such that shifting 'z' forward wraps around to 'a'). Conversely, if direction
is 0
, each character will be shifted backward in the alphabet (again cyclically, so shifting 'a' backward results in 'z').
The goal is to return the modified string after applying all the given shifts.
Intuition
To solve this problem, we need to efficiently apply each shift operation on the string without modifying the string character by character for each operation, which would lead to a large time complexity when many shifts are involved.
The solution approach utilizes the idea of a "difference array" to apply the shifts. The key insight is that shifting a range of characters forward or backward by a certain amount only affects the characters at the start and end boundaries of that range. Hence, we can increment or decrement the shift value at these boundaries and then later track the aggregated shift value for each character.
Here's the step-by-step breakdown of the process:
-
Initialize a "difference array" (
d
) with the same length as the strings
, plus one extra element set to0
. -
Iterate over the
shifts
array:- Convert the direction
0
to-1
for decrementing (backward shifting). - Increment the difference array at the
start
of the shift range by the shift value (which is1
or-1
). - Decrement the difference array at the element just after the
end
of the shift range to cancel the effect for subsequent characters beyond the shift range.
- Convert the direction
-
Process the difference array to convert it into an "aggregate shift array", where each element now represents the total number of shifts that character has gone through.
-
Iterate over the original string, applying the aggregate shift to each character:
- Convert the character to its corresponding numerical value (
ord(s[i]) - ord('a')
). - Add the aggregate shift
d[i]
, wrap it with modulo 26 to keep the value within the alphabet range, and shift it relative toord('a')
to get the final character. - Join the transformed characters to form the final modified string.
- Convert the character to its corresponding numerical value (
By applying the difference array and only after accumulating all shift operations calculating the final characters, the algorithm optimizes the process and keeps the time complexity linear with respect to the length of the string and the number of shift operations.
Learn more about Prefix Sum patterns.
Solution Approach
The solution to this problem involves a clever use of a technique called "Prefix Sum" or, in this specific case, a variation often referred to as the "difference array" approach. This allows us to perform multiple range update queries efficiently and then calculate the aggregate effect of all the updates. Here's a step-by-step explanation of how the solution is implemented:
-
Initialization of the Difference Array (
d
): We start by creating a difference arrayd
with the length of one more than the given strings
. The extra element is to handle the case where the end of a shift range is the last character of the string. This array is initialized to0
since initially, no shifts have been applied.d = [0] * (n + 1)
-
Applying Shifts to the Difference Array: The loop over the shifts array translates each shift operation into an efficient update on the difference array:
for i, j, v in shifts: if v == 0: v = -1 d[i] += v d[j + 1] -= v
If
direction
is0
(backward shift), it's converted to-1
. The valuev
is added to thestart
index and subtracted from the index just afterend
. This setup means that when we later process the difference array, values fromstart
toend
get the proper shift effect applied. -
Accumulating Shift Values: Next, by iterating over the difference array, we convert it from a range-effect array to an accumulation array where each element
d[i]
contains the total shift effect up to that point:for i in range(1, n + 1): d[i] += d[i - 1]
-
Applying the Accumulated Shifts to the String: Finally, we iterate through the original string and apply the accumulated shift effect to each character to obtain the final character after all shifts:
return ''.join( chr(ord('a') + (ord(s[i]) - ord('a') + d[i] + 26) % 26) for i in range(n) )
This is done by converting each character to its numerical equivalent (0 for 'a', 1 for 'b', etc.), adding the shift from
d[i]
(ensuring the result is still a valid character within the a-z range by using modulo 26), and converting it back to a character.
The use of a difference array allows us to apply complex range updates in O(1)
time for each update and then apply the aggregate effect in O(n)
time, giving the overall solution a linear time complexity relative to the size of the input. This makes the algorithm highly efficient for large strings and a large number of shift operations.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's consider a small example to illustrate the solution approach step by step. Assume we have a string s
which is "abcd", and two shift operations given by the 2D array shifts
: [[1, 2, 1], [1, 3, 0]]
.
The first operation shifts characters from index 1 to 2 ('b' and 'c') forward, and the second operation shifts characters from index 1 to 3 ('b', 'c', and 'd') backward.
-
Initialization of the Difference Array (
d
): For string "abcd", we initialize the difference arrayd
of length 5 (since "abcd" has length 4).d = [0, 0, 0, 0, 0]
-
Applying Shifts to the Difference Array:
- Apply the first shift:
shifts[0] = [1, 2, 1]
which means to shift forward the characters at indices 1 and 2.d[1] += 1 # d = [0, 1, 0, 0, 0] d[3] -= 1 # d = [0, 1, 0, -1, 0]
- Apply the second shift:
shifts[1] = [1, 3, 0]
which translates into shifting backward, hencedirection
is0
andv
=-1
.d[1] -= 1 # d = [0, 0, 0, -1, 0] d[4] += 1 # d = [0, 0, 0, -1, 1]
- Apply the first shift:
-
Accumulating Shift Values: Iterate over
d
to accumulate shift values:# Starting from index 1, accumulate the shift values for i in range(1, len(d)): d[i] += d[i - 1] # d becomes [0, 0, 0, -1, 0]
-
Applying the Accumulated Shifts to the String: Iterate through the string, applying the accumulated shifts:
# "a" does not change as d[0] is 0 s[0] = 'a' # "b" would stay as 'b' because d[1] is 0 s[1] = 'b' # "c" would also stay as 'c' because d[2] is 0 s[2] = 'c' # "d" needs to be shifted backward once as d[3] is -1 s[3] = chr(ord('a') + (ord('d') - ord('a') - 1 + 26) % 26) # 'd' -> 'c'
The final modified string after applying all the given shifts is "abcc". The process demonstrates how the shifts are efficiently applied using the difference array approach.
Solution Implementation
1class Solution:
2 def shiftingLetters(self, string: str, shifts: List[List[int]]) -> str:
3 # Length of the input string
4 length_of_string = len(string)
5
6 # Initialize a difference array with an extra space for ease of calculation
7 difference_array = [0] * (length_of_string + 1)
8
9 # Apply each shift operation on the difference array
10 for start, end, direction in shifts:
11 # Convert the shift direction to -1 for left shift, and 1 for right shift
12 value = 1 if direction == 1 else -1
13
14 # Apply the shift direction at the start
15 difference_array[start] += value
16
17 # Reverse the shift direction at the end + 1 to nullify the effect past the end
18 difference_array[end + 1] -= value
19
20 # Convert the difference array to the prefix sum array representing actual shifts
21 for i in range(1, length_of_string + 1):
22 difference_array[i] += difference_array[i - 1]
23
24 # Shift the characters of the original string according to the calculated shifts
25 # and construct the resulting shifted string
26 shifted_string = ''.join(
27 # Shift each character using its ASCII value
28 chr(
29 # Ensure we start counting from 'a' and wrap around using modulo 26 (the alphabet size)
30 ord('a') + (
31 # Find ASCII of current character and add the shift value
32 ord(string[i]) - ord('a') + difference_array[i] + 26
33 ) % 26 # Mod to keep within alphabet range
34 ) for i in range(length_of_string)
35 )
36
37 return shifted_string
38
1class Solution {
2 public String shiftingLetters(String s, int[][] shifts) {
3 int stringLength = s.length();
4 // Difference array to hold the net shift values after performing all shift operations.
5 int[] netShifts = new int[stringLength + 1];
6
7 // Iterate over each shift operation and update the difference array accordingly.
8 for (int[] shift : shifts) {
9 int direction = (shift[2] == 0) ? -1 : 1; // If the shift is left, make it negative.
10 netShifts[shift[0]] += direction; // Apply the shift to the start index.
11 netShifts[shift[1] + 1] -= direction; // Negate the shift after the end index.
12 }
13
14 // Apply the accumulated shifts to get the actual shift values.
15 for (int i = 1; i <= stringLength; ++i) {
16 netShifts[i] += netShifts[i - 1];
17 }
18
19 // Construct the result string after applying the shift to each character.
20 StringBuilder resultStringBuilder = new StringBuilder();
21 for (int i = 0; i < stringLength; ++i) {
22 // Calculate the new character by shifting the current character accordingly.
23 // The mod operation keeps the result within the range of the alphabet,
24 // and the addition of 26 before mod ensures the number is positive.
25 int shiftedIndex = (s.charAt(i) - 'a' + netShifts[i] % 26 + 26) % 26;
26 resultStringBuilder.append((char) ('a' + shiftedIndex));
27 }
28 // Convert the StringBuilder to a String and return the result.
29 return resultStringBuilder.toString();
30 }
31}
32
1class Solution {
2public:
3 string shiftingLetters(string str, vector<vector<int>>& shifts) {
4 int length = str.size();
5 vector<int> delta(length + 1); // Use 'delta' to represent the change in shift for each character
6
7 // Process the shifts
8 for (auto& shift : shifts) {
9 // Additionally, adjust shift[2] to -1 for left shifts instead of 0
10 if (shift[2] == 0) {
11 shift[2] = -1;
12 }
13 delta[shift[0]] += shift[2]; // Apply the shift to the start index
14 delta[shift[1] + 1] -= shift[2]; // Reverse the shift after the end index
15 }
16
17 // Accumulate the shifts to apply
18 for (int i = 1; i <= length; ++i) {
19 delta[i] += delta[i - 1];
20 }
21
22 // Construct the result string with the new shifts applied
23 string result;
24 for (int i = 0; i < length; ++i) {
25 // Calculate new character by adding the shift (wrap around with modulo 26),
26 // also ensure the result is non-negative with an additional +26 before modulo
27 int newCharIndex = (str[i] - 'a' + delta[i] % 26 + 26) % 26;
28 result += ('a' + newCharIndex);
29 }
30 return result;
31 }
32};
33
1function shiftingLetters(str: string, shifts: number[][]): string {
2 const length: number = str.length;
3 const delta: number[] = new Array(length + 1).fill(0); // Use 'delta' to represent the net shift for each character position after all operations
4
5 // Process the shifts
6 for (const shift of shifts) {
7 const start: number = shift[0];
8 const end: number = shift[1];
9 let direction: number = shift[2] === 0 ? -1 : 1; // Left shifts are negative; right shifts are positive
10
11 delta[start] += direction; // Apply the shift at the start index
12 delta[end + 1] -= direction; // Reverse the shift effect after the end index
13 }
14
15 // Apply the cumulative shifts to each character
16 for (let i = 1; i <= length; i++) {
17 delta[i] += delta[i - 1];
18 }
19
20 // Construct the final shifted string
21 let result: string = '';
22 for (let i = 0; i < length; i++) {
23 // Calculate the new character index accounting for wrapping around the alphabet;
24 // Ensure non-negative index with +26 before modulo 26
25 const newCharIndex: number = (str.charCodeAt(i) - 'a'.charCodeAt(0) + delta[i] + 26) % 26;
26 result += String.fromCharCode('a'.charCodeAt(0) + newCharIndex);
27 }
28
29 return result;
30}
31
Time and Space Complexity
Time Complexity
The given code's time complexity can be analyzed as follows:
-
Initializing the difference array
d
withn+1
zeroes takesO(n)
time. -
The shifts loop runs for each element in the
shifts
list (let's say there arem
shift operations). For each shift operation, only constant-time operations are performed (two additions/subtractions), resulting in a time complexity ofO(m)
for this loop. -
The loop for accumulating the shift values in the difference array
d
takesO(n)
time as it iterates through the array once and performs constant-time operations at each index. -
The final loop to construct the shifted string also runs in
O(n)
time, as it iterates through the string once and performs constant-time operations for each character (arithmetic and modulo operations).
The overall time complexity is the sum of all these steps: O(n) + O(m) + O(n) + O(n)
, which can be simplified to O(n + m)
since n
and m
could be of different sizes and each contributes linearly to the total runtime.
Space Complexity
-
The difference array
d
has a length ofn + 1
, giving a space complexity ofO(n)
. -
The final string construction does not use additional space relative to the input size, except for the returned string, which is also of size
n
. However, as this is the output, it is typically not counted towards the space complexity. -
No additional space is used that is dependent on the size of
shifts
.
Therefore, the space complexity is O(n)
, determined by the size of the difference array d
.
Learn more about how to find time and space complexity quickly using problem constraints.
How would you design a stack which has a function min
that returns the minimum element in the stack, in addition to push
and pop
? All push
, pop
, min
should have running time O(1)
.
Recommended Readings
Prefix Sum The prefix sum is an incredibly powerful and straightforward technique Its primary goal is to allow for constant time range sum queries on an array What is Prefix Sum The prefix sum of an array at index i is the sum of all numbers from index 0 to i By
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Donāt Miss This!