⚡Flashcard Drill➔
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

  1. Applying each shift directly is O(n * q), far too slow at these limits.
  2. Use a difference array over the string indices: add +1 at start and -1 at end + 1 for a forward shift, and the opposite for a backward shift.
  3. Then take a running prefix sum to obtain the net shift at each index.
  4. 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 + 1 on the end index: the difference array marks the range as [start, end] inclusive, so the decrement goes at end + 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) % 26 is correct without extra handling.
  • Sizing diff as n instead of n + 1: writing at end + 1 would index out of range when end == n - 1.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Arrays & Hashing Problems