What is the main pattern in Shifting Letters II?

It combines array range updates with string character shifts, solved efficiently using difference arrays and prefix sums.

How do you handle backward shifts in this problem?

Treat backward shifts as negative increments in the difference array and apply modulo 26 when computing final letters.

Can I apply each shift directly on the string?

Direct updates per shift are inefficient for large inputs and may cause timeouts; using a prefix sum array is faster.

How do wrap-around shifts work in Shifting Letters II?

Forward shifts wrap 'z' to 'a' and backward shifts wrap 'a' to 'z', which is handled using modulo 26 arithmetic.

What is the time complexity of the optimal solution?

O(n + m), where n is the length of the string and m is the number of shifts, because each character is shifted once after computing cumulative sums.

#2381

Medium

auto_awesome数组·string

LeetCode 题解工作台

字母移位 II

给你一个小写英文字母组成的字符串 s 和一个二维整数数组 shifts ，其中 shifts[i] = [start i , end i , direction i ] 。对于每个 i ，将 s 中从下标 start i 到下标 end i （两者都包含）所有字符都进行移位运算，如果 directi…

数组字符串前缀和

题目描述

给你一个小写英文字母组成的字符串 s 和一个二维整数数组 shifts ，其中 shifts[i] = [start_i, end_i, direction_i] 。对于每个 i ，将 s 中从下标 start_i 到下标 end_i （两者都包含）所有字符都进行移位运算，如果 direction_i = 1 将字符向后移位，如果 direction_i = 0 将字符向前移位。

将一个字符向后移位的意思是将这个字符用字母表中 下一个 字母替换（字母表视为环绕的，所以 'z' 变成 'a'）。类似的，将一个字符向前移位的意思是将这个字符用字母表中 前一个 字母替换（字母表是环绕的，所以 'a' 变成 'z' ）。

请你返回对 s 进行所有移位操作以后得到的最终字符串。

示例 1：

输入：s = "abc", shifts = [[0,1,0],[1,2,1],[0,2,1]]
输出："ace"
解释：首先，将下标从 0 到 1 的字母向前移位，得到 s = "zac" 。
然后，将下标从 1 到 2 的字母向后移位，得到 s = "zbd" 。
最后，将下标从 0 到 2 的字符向后移位，得到 s = "ace" 。

示例 2:

输入：s = "dztz", shifts = [[0,0,0],[1,1,1]]
输出："catz"
解释：首先，将下标从 0 到 0 的字母向前移位，得到 s = "cztz" 。
最后，将下标从 1 到 1 的字符向后移位，得到 s = "catz" 。

提示：

1 <= s.length, shifts.length <= 5 * 10⁴
shifts[i].length == 3
0 <= start_i <= end_i < s.length
0 <= direction_i <= 1
s 只包含小写英文字母。

lightbulb

解题思路

方法一：差分数组

用差分数组 $d$ 记录区间的变化，然后对 $d$ 求前缀和，得到每个下标 $i$ 的变化量 $d[i]$ 。

然后将原字符串中每个字符加上对应的 $d[i]$ ，最终得到一个新的字符串。

时间复杂度 $O(n+m)$ 。其中 $n$ 是原字符串 $s$ 的长度，而 $m$ 是移位操作 $shifts$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

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)
        )

speed

复杂度分析

指标	值
时间	complexity is O(n + m) where n is the string length and m is the number of shifts, as we process shifts in a difference array and apply cumulative shifts once. Space complexity is O(n) for the difference array storing net shifts.
空间	O(n)

psychology

面试官常问的追问

外企场景

question_mark
Can you avoid applying each shift individually?
question_mark
What if the shifts array is very large and direct updates are too slow?
question_mark
How can prefix sums optimize cumulative letter transformations?

warning

常见陷阱

外企场景

error
Forgetting to wrap around 'z' to 'a' or 'a' to 'z'.
error
Incorrectly applying backward shifts as negative increments without proper modulo handling.
error
Updating characters per shift instead of using a prefix sum leads to timeouts on large inputs.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Shifting letters with non-overlapping ranges only.
arrow_right_alt
Shifting letters with variable shift amounts instead of single-step forward/backward.
arrow_right_alt
Applying shifts on strings with uppercase letters, requiring separate ASCII handling.

help

常见问题

外企场景

继续练习

#2391 收集垃圾的最少总时间 #2559 统计范围内的元音字符串数 #2055 蜡烛之间的盘子