Shifting Letters II

Med

#2167Time: O(M * N), where N is the length of the string `s` and M is the number of shifts. For each of the M shifts, we might iterate up to N characters in the worst case.Space: O(N) to store the character array, as strings are immutable in Java.1 company

Patterns

Prefix Sum

Data structures

Array String

Companies

Veritas

Prompt

You are given a string s of lowercase English letters and a 2D integer array shifts where shifts[i] = [start_i, end_i, direction_i]. For every i, shift the characters in s from the index start_i to the index end_i (inclusive) forward if direction_i = 1, or shift the characters backward if direction_i = 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 * 10⁴
shifts[i].length == 3
0 <= start_i <= end_i < s.length
0 <= direction_i <= 1
s consists of lowercase English letters.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach directly simulates the process described in the problem. It iterates through each shift instruction and applies the specified shift to every character within the given range.

Algorithm

Convert the input string s into a character array chars.
Iterate through each shift in the shifts array.
For each shift = [start, end, direction]:
- Determine the shift amount: 1 for forward, -1 for backward.
- Iterate from i = start to i = end.
- Calculate the new character for chars[i] by applying the shift amount. Handle wrapping around the alphabet (e.g., using the modulo operator: (original_position + shift_amount + 26) % 26).
- Update chars[i] with the new character.
After all shifts are processed, convert the chars array back to a string and return it.

Walkthrough

The core idea is to treat the input string as a mutable sequence of characters, like a character array. We loop through every command in the shifts array. For each command [start, end, direction], we run another loop from the start index to the end index. Inside this inner loop, we modify the character at the current position. If the direction is forward (1), we increment the character, wrapping around from 'z' to 'a'. If the direction is backward (0), we decrement it, wrapping from 'a' to 'z'. This process is repeated for all shifts. Finally, the modified character array is converted back into a string.

Here is a Java implementation of this approach:

1class Solution {2    public String shiftingLetters(String s, int[][] shifts) {3        char[] chars = s.toCharArray();4        for (int[] shift : shifts) {5            int start = shift[0];6            int end = shift[1];7            int direction = shift[2];8            int amount = (direction == 1) ? 1 : -1;9 10            for (int i = start; i <= end; i++) {11                int originalPos = chars[i] - 'a';12                int newPos = (originalPos + amount + 26) % 26;13                chars[i] = (char) ('a' + newPos);14            }15        }16        return new String(chars);17    }18}

Complexity

Time

O(M * N), where N is the length of the string `s` and M is the number of shifts. For each of the M shifts, we might iterate up to N characters in the worst case.

Space

O(N) to store the character array, as strings are immutable in Java.

Trade-offs

Pros

Very straightforward to understand and implement.
It follows the problem description literally.

Cons

Highly inefficient. The time complexity is the product of the number of shifts and the length of the string, which is too slow for the given constraints.
Will result in a 'Time Limit Exceeded' (TLE) error on larger test cases.

A much more efficient approach involves calculating the net effect of all shifts on each character before modifying the string. Instead of applying shifts one by one, we can determine the final total shift for each position in a single pass. This can be achieved using a technique called a difference array or line sweep.

Algorithm

Create an integer array line of size n (where n is the length of s), initialized to all zeros.
Iterate through each shift = [start, end, direction] in shifts:
- Determine the shift value: val = 1 for forward, val = -1 for backward.
- Increment line[start] by val.
- If end + 1 < n, decrement line[end + 1] by val.
Initialize a variable currentShift = 0.
Create a StringBuilder or character array to build the result.
Iterate from i = 0 to n-1:
- Update the net shift for the current position: currentShift += line[i].
- Calculate the new character for s[i] by applying currentShift. Use modulo arithmetic to handle wrapping: new_char_code = (s[i] - 'a' + currentShift) % 26.
- Ensure the result of the modulo is non-negative (e.g., (val % 26 + 26) % 26).
- Append the new character to the result.
Return the final string.

Walkthrough

The key insight is that a shift applied to a range [start, end] can be recorded by making two updates: one at the start index and an opposite one at the end + 1 index. We create an auxiliary array, let's call it line, of size n (the length of the string), initialized to zeros. For each shift [start, end, direction], we add +1 (for forward) or -1 (for backward) to line[start]. Then, we subtract the same value at line[end + 1] (if it's within bounds). This marks the start and end of the shift's influence.

After processing all shifts this way, the line array holds the changes in shift values. By calculating the prefix sum of the line array, we can find the cumulative, or net, shift for each position. For example, the net shift at index i is the sum of all values in line from 0 to i. Once we have the net shift for every character, we iterate through the original string just once, apply the calculated net shift to each character, and build the final result string.

Here is a Java implementation of this efficient approach:

1class Solution {2    public String shiftingLetters(String s, int[][] shifts) {3        int n = s.length();4        int[] line = new int[n];5 6        for (int[] shift : shifts) {7            int start = shift[0];8            int end = shift[1];9            int val = (shift[2] == 1) ? 1 : -1;10 11            line[start] += val;12            if (end + 1 < n) {13                line[end + 1] -= val;14            }15        }16 17        char[] resultChars = s.toCharArray();18        int currentShift = 0;19        for (int i = 0; i < n; i++) {20            currentShift += line[i];21            int originalPos = resultChars[i] - 'a';22            // The total shift can be large, so we use modulo. 23            // The formula (val % 26 + 26) % 26 handles negative results correctly.24            int newPos = (originalPos + (currentShift % 26) + 26) % 26;25            resultChars[i] = (char) ('a' + newPos);26        }27 28        return new String(resultChars);29    }30}

Complexity

Time

O(N + M), where N is the length of `s` and M is the number of shifts. We iterate through `shifts` once (O(M)) and then iterate through the string and the `line` array once (O(N)).

Space

O(N) to store the difference array `line`.

Trade-offs

Pros

Highly efficient with a linear time complexity.
Passes all test cases within the given constraints.
It's a standard and powerful technique for problems involving range updates.

Cons

Requires more space than the brute-force approach (O(N) vs O(1) if string modification in-place was possible).
The concept of a difference array might be less intuitive for beginners.

Solutions

Solution

1class Solution {2public3  String shiftingLetters(String s, int[][] shifts) {4    int n = s.length();5    int[] d = new int[n + 1];6    for (int[] e : shifts) {7      if (e[2] == 0) {8        e[2]--;9      }10      d[e[0]] += e[2];11      d[e[1] + 1] -= e[2];12    }13    for (int i = 1; i <= n; ++i) {14      d[i] += d[i - 1];15    }16    StringBuilder ans = new StringBuilder();17    for (int i = 0; i < n; ++i) {18      int j = (s.charAt(i) - 'a' + d[i] % 26 + 26) % 26;19      ans.append((char)('a' + j));20    }21    return ans.toString();22  }23}

1class Solution {2public:3  string shiftingLetters(string s, vector<vector<int>> &shifts) {4    int n = s.size();5    vector<int> d(n + 1);6    for (auto &e : shifts) {7      if (e[2] == 0) {8        e[2]--;9      }10      d[e[0]] += e[2];11      d[e[1] + 1] -= e[2];12    }13    for (int i = 1; i <= n; ++i) {14      d[i] += d[i - 1];15    }16    string ans;17    for (int i = 0; i < n; ++i) {18      int j = (s[i] - 'a' + d[i] % 26 + 26) % 26;19      ans += ('a' + j);20    }21    return ans;22  }23};

1class Solution:2    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str: n = len(s) d = [0] * (n + 1) for i, j, v in shifts: if v == 0: v = - 1 d[i] += v d[j + 1] -= v for i in range(1, n + 1): d[i] += d[i - 1] return '' . join(chr(ord('a') + (ord(s[i]) - ord('a') + d[i] + 26) % 26) for i in range(n))

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem