Intuition

We want to accumulate all the shifts operations, and compute the final string with the minimal effort.

Approach

Step 1: Replace each operation in shifts with two equivalent operations’ combination (in mind)

This is something like a reverse operation of “Prefix Sum”. Let’s take a look at one element in the array shifts, for example, shifts[i] = [start_i, end_i, direction_i]. This indicates we need to shift the characters in s from the index start_i to the index end_i in one direction (which is decided by the value of direction_i). This operation is equivalent to the combination of two operations:

• shift the characters in s from the index 0 to the index end_i in one direction, and
• shift the characters in s from the index 0 to the index start_i - 1 in the opposite direction

In other words, each [start, end, d] in shifts can be replaced with one [0, end, d] and one [0, start - 1, 1 - d].

Step 2: Accumulate operations in shifts in a new array

Let’s create a new array eq_shifts, where eq_shifts[i] represents the count of forward operations that applied to the characters in s from the index 0 to the index i (inclusive).

• Iterate through the shifts array, at index i, we do
  • eq_shifts[shifts[1]] += step
  • eq_shifts[shifts[0] - 1] -= step
    • only in the case of shifts[0] - 1 >= 0
  • where step = 1 if d == 1, otherwise step = -1

Step 3: Understand the problem with the new description

Now, this problem has been re-written as follows:

Given string s, and array eq_shifts. For each eq_shifts[i] = x, we want to shift (forward) the first i + 1 letters of s, x times. Return the final string after all such shifts to s are applied.

This is exactly the problem 848. Shifting Letters, which can be solved by “Suffix Sum”.

Let’s take a look at the “power” of each eq_shifts[i]. It can move all letters within the range of [0, i] in string s by eq_shifts[i] times.

eq_shifts[0] --> s[0]
eq_shifts[1] --> s[0], s[1]
eq_shifts[2] --> s[0], s[1], s[2]
            ...
eq_shifts[i] --> s[0], ..., s[i]
            ...
eq_shifts[n - 1] --> s[0], ..., s[n - 1]

In another point of view, each s[i] is “controlled” by the sum of elements within the range of [i, n - 1] in array eq_shifts.

s[0] --> sum(eq_shifts[0], ..., eq_shifts[n - 1])
s[1] --> sum(eq_shifts[1], ..., eq_shifts[n - 1])
     ...
s[i] --> sum(eq_shifts[i], ..., eq_shifts[n - 1])
     ...
s[n - 1] --> sum(eq_shifts[n - 1])

Step 4: Solve the problem with “Suffix Sum”

This is a typical structure of “Prefix/Suffix Sum” problem. Use a new array suffix_sum to denote the “suffix sum”, where

This can be computed by iterating through the array eq_shifts from right to left.

• Initialize count = 0, at each index i, add count by eq_shifts[i], then suffix_sum[i] = count.

To optimize the usage of space, we don’t need the array suffix_sum, but only the count, which represents the count of “shift forward” operations applied to s[i].

Side Note: How to compute shift(letter, x)?

• Firstly, x can be simplified by x = x % 26; and x = x + 26 (in the case of negative x).
• Imagine a array containing all low-case letters, letters = ['a','b',...'z'], the index of shift(letter, x) can be computed by (index_of(letter) + x) % 26, where index_of(letter) is the index of letter in array letters.
• In reality, however, letters = ['a','b',...'z'] is a sub-array of all ASCII characters, where ascii_of('a') is 97, ascii_of('b') is 98 and so on.
• Since index_of(letter) = ascii_of(letter) - ascii_of('a'), the index of shift(letter, x), i.e.,(index_of(letter) + x) % 26, can be written as (ascii_of(letter) - ascii_of('a') + x) % 26.
• Furthermore, the ASCII value of shift(letter, x) can be obtained by ascii_of('a') + (ascii_of(letter) - ascii_of('a') + x) % 26.
• Finally, we just need to convert the ASCII value to the character.

Code

• Python3
• C++

• class Solution:
      def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:
          n = len(s)
          eq_shifts = [0] * len(s)
          for start, end, d in shifts:
              step = 1 if d == 1 else -1
              eq_shifts[end] += step
              if start - 1 >= 0:
                  eq_shifts[start - 1] -= step
          cnt = 0
          res = [""] * n
          for i in range(n - 1, -1, -1):
              cnt = (cnt + eq_shifts[i]) % 26
              if cnt < 0:
                  cnt += 26
              res[i] = chr(ord("a") + (ord(s[i]) - ord("a") + cnt) % 26)
  
          return "".join(res)
  

• class Solution {
  public:
      string shiftingLetters(string s, vector<vector<int>>& shifts) {
          int n = s.size();
          vector<int> eq_shifts(n, 0);
          for (auto shift : shifts) {
              int step = shift[2] == 1 ? 1 : -1;
              eq_shifts[shift[1]] += step;
              if (shift[0] - 1 >= 0) {
                  eq_shifts[shift[0] - 1] -= step;
              }
          }
          string res(n, ' ');
          int cnt = 0;
          for (int i = n - 1; i >= 0; i--) {
              cnt = (cnt + eq_shifts[i]) % 26;
              if (cnt < 0) {
                  cnt += 26;
              }
              res[i] = 'a' + (s[i] - 'a' + cnt) % 26;
          }
          return res;
      }
  };
  

Complexity

• Time complexity: $O(M+N)$
  • $N$ is the length of s and $M$ is the length of shifts.
• Space complexity: $O(N)$
  • eq_shifts takes $O(N)$ space.