# Shifting Letters II
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/shifting-letters-ii)
Canonical: https://scaleengineer.com/dsa/problems/shifting-letters-ii
**Patterns:** [Prefix Sum](https://scaleengineer.com/dsa/patterns/prefix-sum)
**Data structures:** Array, String
**Companies:** [Veritas](https://scaleengineer.com/companies/veritas)
---
## 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_.

**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.

# Approaches
## Brute Force Simulation
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.
**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.
**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.
### Explanation
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:
```java
class Solution {
    public String shiftingLetters(String s, int[][] shifts) {
        char[] chars = s.toCharArray();
        for (int[] shift : shifts) {
            int start = shift[0];
            int end = shift[1];
            int direction = shift[2];
            int amount = (direction == 1) ? 1 : -1;

            for (int i = start; i <= end; i++) {
                int originalPos = chars[i] - 'a';
                int newPos = (originalPos + amount + 26) % 26;
                chars[i] = (char) ('a' + newPos);
            }
        }
        return new String(chars);
    }
}
```
### 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.

## Efficient Approach using Difference Array (Line Sweep)
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.
**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`.
**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.
### Explanation
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:
```java
class Solution {
    public String shiftingLetters(String s, int[][] shifts) {
        int n = s.length();
        int[] line = new int[n];

        for (int[] shift : shifts) {
            int start = shift[0];
            int end = shift[1];
            int val = (shift[2] == 1) ? 1 : -1;

            line[start] += val;
            if (end + 1 < n) {
                line[end + 1] -= val;
            }
        }

        char[] resultChars = s.toCharArray();
        int currentShift = 0;
        for (int i = 0; i < n; i++) {
            currentShift += line[i];
            int originalPos = resultChars[i] - 'a';
            // The total shift can be large, so we use modulo. 
            // The formula (val % 26 + 26) % 26 handles negative results correctly.
            int newPos = (originalPos + (currentShift % 26) + 26) % 26;
            resultChars[i] = (char) ('a' + newPos);
        }

        return new String(resultChars);
    }
}
```
### 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.

# Solutions
### Java

```java
class Solution {
public
  String shiftingLetters(String s, int[][] shifts) {
    int n = s.length();
    int[] d = new int[n + 1];
    for (int[] e : shifts) {
      if (e[2] == 0) {
        e[2]--;
      }
      d[e[0]] += e[2];
      d[e[1] + 1] -= e[2];
    }
    for (int i = 1; i <= n; ++i) {
      d[i] += d[i - 1];
    }
    StringBuilder ans = new StringBuilder();
    for (int i = 0; i < n; ++i) {
      int j = (s.charAt(i) - 'a' + d[i] % 26 + 26) % 26;
      ans.append((char)('a' + j));
    }
    return ans.toString();
  }
}

```

### CPP

```cpp
class Solution {
public:
  string shiftingLetters(string s, vector<vector<int>> &shifts) {
    int n = s.size();
    vector<int> d(n + 1);
    for (auto &e : shifts) {
      if (e[2] == 0) {
        e[2]--;
      }
      d[e[0]] += e[2];
      d[e[1] + 1] -= e[2];
    }
    for (int i = 1; i <= n; ++i) {
      d[i] += d[i - 1];
    }
    string ans;
    for (int i = 0; i < n; ++i) {
      int j = (s[i] - 'a' + d[i] % 26 + 26) % 26;
      ans += ('a' + j);
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    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))

```