# 2381. Shifting Letters II
[2381. Shifting Letters II](https://leetcode.com/problems/shifting-letters-ii/) (<font color="#FFB800"> Medium</font> 通過率: 45.4%)

## 限制條件
<ul>
<li>1 <= s.length, shifts.length <= 5 * 10^4</li>
<li>shifts[i].length == 3</li>
<li>0 <= starti <= endi < s.length</li>
<li>0 <= directioni <= 1</li>
</ul>

### 解法 1
將每一個運算利用 vector 寫下，但這樣的方法會超時。

- 時間複雜度: $O(N^2)$
- 空間複雜度: $O(N)$

class Solution {
public:

    string shiftingLetters(string s, vector<vector<int>>& shifts) {
        vector<int> record(s.size());
        for (auto& shift : shifts) {
            for (int i = shift[0]; i <= shift[1] && i < record.size(); i++) {
                if (shift[2] == 1) {
                    record[i] = record[i] + 1;
                } else {
                    record[i] = record[i] - 1;
                }
            }
        }

        for (int i = 0; i < s.size(); i++) {
            record[i] %= 26;
            while (record[i] >= 26) {
                record[i] -= 26;
            }
            while (record[i] < 0) {
                record[i] += 26;
            }
            s[i] = (s[i] - 'a' + record[i]) % 26 + 'a';
        }
        return s;
    }
};

### 解法 2
使用 [Difference Array](https://codeforces.com/blog/entry/78762) 來解，可以減少每一次offset 的運算

- 時間複雜度: $O(N)$
- 空間複雜度: $O(N)$

class Solution {
public:
    string shiftingLetters(string s, vector<vector<int>>& shifts) {
        vector<int> records(s.size() + 1);
        for (auto& shift : shifts) {
            int start = shift[0], end = shift[1], direction = shift[2];
            records[start] += (direction == 1 ? 1 : -1);
            records[end + 1] -= (direction == 1 ? 1 : -1);
        }

        int currentShift = 0;
        for (int i = 0; i < s.size(); ++i) {
            currentShift += records[i];
            records[i] = currentShift;
        }

        for (int i = 0; i < s.size(); i++) {
            records[i] %= 26;
            while (records[i] >= 26) {
                records[i] -= 26;
            }
            while (records[i] < 0) {
                records[i] += 26;
            }
            s[i] = (s[i] - 'a' + records[i]) % 26 + 'a';
        }
        return s;
    }
};