NeetCode #135LC-2381MediumArrays & Hashing
← Back to All Problems#135 · #2381 · Shifting Letters II(字母移位 II)
📌 Problem Statement & Constraints
You are given a lowercase string
s and a list of shifts, each shifts[i] = [start_i, end_i, direction_i]. Direction 1 shifts the letters in s[start..end] forward by 1 in the alphabet (wrapping z to a); direction 0 shifts them backward. Return the final string. Constraints: 1 <= s.length <= 5 * 10^4, 1 <= shifts.length <= 5 * 10^4.💡 Core Algorithmic Approaches
- Applying each shift directly is O(n * q), far too slow at these limits.
- Use a difference array over the string indices: add
+1atstartand-1atend + 1for a forward shift, and the opposite for a backward shift. - Then take a running prefix sum to obtain the net shift at each index.
- Finally apply the net shift to each character with modulo 26. This makes the whole thing O(n + q).
💻 Benchmark Python3 Implementation
class Solution:
def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:
n = len(s)
diff = [0] * (n + 1)
for start, end, d in shifts:
v = 1 if d == 1 else -1
diff[start] += v # range start
diff[end + 1] -= v # one past the range end
res = []
cur = 0
for i in range(n):
cur += diff[i] # net shift at index i
res.append(chr((ord(s[i]) - 97 + cur) % 26 + 97))
return "".join(res)⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n + q): building the difference array is O(q) and applying it is O(n).
💾 Space Complexity
O(n) for the difference array (or O(1) extra beyond the output if the string is built in place).
⚠️ Interview Pitfalls & Follow-ups
- Applying each shift character by character: O(n * q) = 2.5 * 10^9 operations, which will time out.
- Forgetting the
+ 1on the end index: the difference array marks the range as[start, end]inclusive, so the decrement goes atend + 1. Off by one here silently corrupts every character after the range. - Not taking the modulo of a negative shift: Python's
%returns a non-negative result for a positive modulus, so(x - 5) % 26is correct without extra handling. - Sizing
diffasninstead ofn + 1: writing atend + 1would index out of range whenend == n - 1.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.