2381. Shifting Letters II

MediumArrayStringPrefix Sum
Leetcode Link

Problem Description

You are given a string s consisting of lowercase English letters and a 2D integer array shifts. Each element in shifts is represented as [start_i, end_i, direction_i] where:

  • start_i and end_i define a range of indices in the string (inclusive)
  • direction_i determines the shift direction:
    • If direction_i = 1, shift characters forward
    • If direction_i = 0, shift characters backward

Shifting rules:

  • Forward shift: Replace each character with the next letter in the alphabet. The letter 'z' wraps around to become 'a'.
  • Backward shift: Replace each character with the previous letter in the alphabet. The letter 'a' wraps around to become 'z'.

For each shift operation in the shifts array, you need to apply the specified shift to all characters from index start_i to index end_i (inclusive).

Example:

  • If you shift 'a' forward, it becomes 'b'
  • If you shift 'z' forward, it becomes 'a' (wrapping)
  • If you shift 'b' backward, it becomes 'a'
  • If you shift 'a' backward, it becomes 'z' (wrapping)

The task is to apply all the shift operations in sequence and return the final transformed string after all shifts have been applied.

Quick Interview Experience
Help others by sharing your interview experience
Have you seen this problem before?

Intuition

The naive approach would be to process each shift operation one by one, iterating through the specified range and modifying each character. However, if we have many overlapping shifts, this becomes inefficient as we might update the same character multiple times.

The key insight is that we can track the cumulative effect of all shifts on each character position. Instead of applying shifts immediately, we can:

  1. Record how many total shifts (forward or backward) each character needs
  2. Apply all the accumulated shifts at once at the end

This leads us to think about a difference array technique. Rather than updating every element in a range for each shift operation, we can:

  • Mark the beginning of a range with +shift_value
  • Mark the position after the end of the range with -shift_value

For example, if we want to shift indices [1, 3] forward by 1:

  • We add +1 at index 1
  • We add -1 at index 4 (one position after index 3)

When we compute the prefix sum of this difference array, we automatically get the total number of shifts needed at each position. This is because:

  • The prefix sum "carries forward" the shift value starting from the begin index
  • The negative value at end+1 cancels out the shift for positions beyond the range

For backward shifts (when direction = 0), we treat them as negative shifts (-1) instead of positive ones.

Finally, once we have the total shift count for each position, we can apply all shifts in a single pass. We use modulo 26 arithmetic to handle the wrapping behavior of the alphabet (since there are 26 letters, shifting by 26 brings us back to the same letter).

Learn more about Prefix Sum patterns.

Solution Implementation

1class Solution: 2 def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str: 3 # Get the length of the string 4 n = len(s) 5 6 # Initialize difference array with n+1 elements for range updates 7 # This will track cumulative shift values for each position 8 diff_array = [0] * (n + 1) 9 10 # Process each shift operation 11 for start_idx, end_idx, direction in shifts: 12 # Convert direction: 0 means shift backward (-1), 1 means shift forward (+1) 13 if direction == 0: 14 direction = -1 15 16 # Apply range update using difference array technique 17 # Add shift value at start position 18 diff_array[start_idx] += direction 19 # Subtract shift value at position after end to cancel effect 20 diff_array[end_idx + 1] -= direction 21 22 # Calculate prefix sum to get actual shift values for each position 23 for i in range(1, n + 1): 24 diff_array[i] += diff_array[i - 1] 25 26 # Build the result string by applying shifts to each character 27 result_chars = [] 28 for i in range(n): 29 # Get the original character's position relative to 'a' 30 original_pos = ord(s[i]) - ord('a') 31 32 # Apply the shift and handle wrap-around using modulo 33 # Add 26 before modulo to handle negative shifts correctly 34 new_pos = (original_pos + diff_array[i] + 26) % 26 35 36 # Convert back to character and add to result 37 result_chars.append(chr(ord('a') + new_pos)) 38 39 # Join all characters to form the final string 40 return ''.join(result_chars) 41
1class Solution { 2 public String shiftingLetters(String s, int[][] shifts) { 3 int stringLength = s.length(); 4 5 // Create a difference array to track cumulative shifts 6 // Extra space at the end for boundary handling 7 int[] differenceArray = new int[stringLength + 1]; 8 9 // Process each shift operation 10 for (int[] shift : shifts) { 11 int startIndex = shift[0]; 12 int endIndex = shift[1]; 13 int direction = shift[2]; 14 15 // Convert direction: 0 (backward) becomes -1, 1 (forward) stays 1 16 if (direction == 0) { 17 direction = -1; 18 } 19 20 // Apply difference array technique for range updates 21 // Add shift value at start position 22 differenceArray[startIndex] += direction; 23 // Subtract shift value after end position to limit the range 24 differenceArray[endIndex + 1] -= direction; 25 } 26 27 // Convert difference array to actual shift values using prefix sum 28 for (int i = 1; i <= stringLength; i++) { 29 differenceArray[i] += differenceArray[i - 1]; 30 } 31 32 // Build the result string by applying shifts to each character 33 StringBuilder result = new StringBuilder(); 34 35 for (int i = 0; i < stringLength; i++) { 36 // Get the original character's position (0-25) 37 int originalPosition = s.charAt(i) - 'a'; 38 39 // Apply the shift and handle both positive and negative shifts 40 // The formula ensures proper wrapping within 'a' to 'z' 41 int shiftAmount = differenceArray[i] % 26; 42 int newPosition = (originalPosition + shiftAmount + 26) % 26; 43 44 // Convert back to character and append to result 45 result.append((char) ('a' + newPosition)); 46 } 47 48 return result.toString(); 49 } 50} 51
1class Solution { 2public: 3 string shiftingLetters(string s, vector<vector<int>>& shifts) { 4 int n = s.size(); 5 6 // Create a difference array to track cumulative shifts 7 // Size is n+1 to handle the end boundary 8 vector<int> diffArray(n + 1, 0); 9 10 // Process each shift operation 11 for (auto& shift : shifts) { 12 int startIdx = shift[0]; 13 int endIdx = shift[1]; 14 int direction = shift[2]; 15 16 // Convert direction: 0 means backward (-1), 1 means forward (+1) 17 if (direction == 0) { 18 direction = -1; 19 } 20 21 // Apply difference array technique for range update 22 // Add shift value at start position 23 diffArray[startIdx] += direction; 24 // Subtract shift value after end position to limit the range 25 diffArray[endIdx + 1] -= direction; 26 } 27 28 // Convert difference array to actual shift values using prefix sum 29 for (int i = 1; i <= n; ++i) { 30 diffArray[i] += diffArray[i - 1]; 31 } 32 33 // Build the result string by applying shifts to each character 34 string result = ""; 35 for (int i = 0; i < n; ++i) { 36 // Calculate the shifted character position 37 // Use modulo 26 to handle wraparound, add 26 to handle negative values 38 int originalPos = s[i] - 'a'; 39 int shiftAmount = diffArray[i] % 26; 40 int newPos = (originalPos + shiftAmount + 26) % 26; 41 42 // Append the shifted character to result 43 result += ('a' + newPos); 44 } 45 46 return result; 47 } 48}; 49
1/** 2 * Shifts letters in a string based on multiple shift operations 3 * @param s - The input string to be shifted 4 * @param shifts - Array of shift operations, each containing [startIndex, endIndex, direction] 5 * where direction is 1 for forward shift and 0 for backward shift 6 * @returns The string after applying all shift operations 7 */ 8function shiftingLetters(s: string, shifts: number[][]): string { 9 const stringLength: number = s.length; 10 // Difference array to track cumulative shifts at each position 11 const differenceArray: number[] = new Array(stringLength + 1).fill(0); 12 13 // Process each shift operation using difference array technique 14 for (const [startIndex, endIndex, direction] of shifts) { 15 // Convert direction: 1 stays as 1 (forward), 0 becomes -1 (backward) 16 let shiftValue: number = direction; 17 if (shiftValue === 0) { 18 shiftValue = -1; 19 } 20 21 // Mark the start and end of the shift range 22 differenceArray[startIndex] += shiftValue; 23 differenceArray[endIndex + 1] -= shiftValue; 24 } 25 26 // Calculate prefix sum to get actual shift values at each position 27 for (let i = 1; i <= stringLength; i++) { 28 differenceArray[i] += differenceArray[i - 1]; 29 } 30 31 // Build the result string by applying shifts to each character 32 let resultString: string = ''; 33 for (let i = 0; i < stringLength; i++) { 34 // Calculate the new character position after shifting 35 // Handle both positive and negative shifts with modulo arithmetic 36 const originalPosition: number = s.charCodeAt(i) - 'a'.charCodeAt(0); 37 const shiftAmount: number = differenceArray[i] % 26; 38 const newPosition: number = (originalPosition + shiftAmount + 26) % 26; 39 40 // Convert back to character and append to result 41 resultString += String.fromCharCode('a'.charCodeAt(0) + newPosition); 42 } 43 44 return resultString; 45} 46

Solution Approach

The solution uses a difference array technique to efficiently handle multiple range updates:

1. Initialize the difference array:

d = [0] * (n + 1)

We create an array d of size n + 1 (one extra element to handle the boundary) to track the shift differences.

2. Process each shift operation:

for i, j, v in shifts:  if v == 0:  v = -1  d[i] += v  d[j + 1] -= v

For each shift [start, end, direction]:

  • Convert backward shifts (v = 0) to -1 to represent negative shifts
  • Add the shift value v at index i (start of range)
  • Subtract the shift value v at index j + 1 (one position after the end of range)

This marks the boundaries of each shift range without updating every element in between.

3. Compute prefix sum to get actual shifts:

for i in range(1, n + 1):  d[i] += d[i - 1]

The prefix sum transforms the difference array into the actual number of shifts needed at each position. After this step, d[i] contains the total net shifts for character at index i.

4. Apply shifts and build the result:

return ''.join(  chr(ord('a') + (ord(s[i]) - ord('a') + d[i] + 26) % 26) for i in range(n) )

For each character at position i:

  • Convert the character to its position in the alphabet: ord(s[i]) - ord('a') (gives 0-25)
  • Add the total shift amount: d[i]
  • Add 26 before taking modulo to handle negative shifts properly
  • Apply modulo 26 to handle wrapping: % 26
  • Convert back to a character: chr(ord('a') + result)

Time Complexity: O(m + n) where m is the number of shifts and n is the length of the string. Space Complexity: O(n) for the difference array.

The beauty of this approach is that regardless of how many overlapping shifts we have, we only need to:

  • Make two updates per shift operation (at boundaries)
  • Perform one prefix sum computation
  • Apply shifts once at the end

This is much more efficient than the naive approach which would be O(m * k) where k is the average range size.

Ready to land your dream job?

Unlock your dream job with a 5-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a concrete example to illustrate the solution approach.

Input:

  • s = "abc"
  • shifts = [[0, 1, 1], [1, 2, 0], [0, 2, 1]]

Step 1: Initialize the difference array

s = "abc" (length n = 3) d = [0, 0, 0, 0] (size n + 1 = 4)

Step 2: Process each shift operation

First shift [0, 1, 1]: Shift forward indices 0 to 1

  • Since direction = 1, v = 1
  • d[0] += 1 → d = [1, 0, 0, 0]
  • d[2] -= 1 → d = [1, 0, -1, 0]

Second shift [1, 2, 0]: Shift backward indices 1 to 2

  • Since direction = 0, v = -1
  • d[1] += -1 → d = [1, -1, -1, 0]
  • d[3] -= -1 → d = [1, -1, -1, 1]

Third shift [0, 2, 1]: Shift forward indices 0 to 2

  • Since direction = 1, v = 1
  • d[0] += 1 → d = [2, -1, -1, 1]
  • d[3] -= 1 → d = [2, -1, -1, 0]

Step 3: Compute prefix sum

d[0] = 2 d[1] = d[0] + d[1] = 2 + (-1) = 1 d[2] = d[1] + d[2] = 1 + (-1) = 0 d[3] = d[2] + d[3] = 0 + 0 = 0

Final d = [2, 1, 0, 0]

This means:

  • Index 0 needs 2 forward shifts
  • Index 1 needs 1 forward shift
  • Index 2 needs 0 shifts

Step 4: Apply shifts to build result

Position 0: Character 'a'

  • Position in alphabet: 0
  • Add shifts: 0 + 2 = 2
  • New position: 2 → 'c'

Position 1: Character 'b'

  • Position in alphabet: 1
  • Add shifts: 1 + 1 = 2
  • New position: 2 → 'c'

Position 2: Character 'c'

  • Position in alphabet: 2
  • Add shifts: 2 + 0 = 2
  • New position: 2 → 'c'

Final Result: "ccc"

The difference array technique allowed us to handle three overlapping shift operations efficiently by:

  1. Recording only boundary changes (2 updates per shift)
  2. Computing the cumulative effect with a single prefix sum pass
  3. Applying all accumulated shifts in one final pass

Time and Space Complexity

Time Complexity: O(m + n) where n is the length of string s and m is the number of shift operations in the shifts list.

  • Processing all shift operations: The first loop iterates through all m shift operations, each taking O(1) time to update the difference array. This takes O(m) time.
  • Computing prefix sum: The second loop runs from index 1 to n to calculate the cumulative sum of the difference array. This takes O(n) time.
  • Building result string: The final list comprehension iterates through all n characters, performing O(1) operations for each character transformation. This takes O(n) time.
  • Total: O(m) + O(n) + O(n) = O(m + n)

Space Complexity: O(n) where n is the length of string s.

  • Difference array d: Creates an array of size n + 1 to store the difference values, requiring O(n) space.
  • Result string: The join operation creates a new string of length n, which requires O(n) space.
  • Other variables: Only constant extra space is used for loop variables and temporary calculations.
  • Total: O(n) + O(n) = O(n)

The algorithm uses a difference array technique to efficiently handle range updates, avoiding the need to update each character individually for every shift operation, which would result in O(m * n) time complexity.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Handling of Negative Shifts (Modulo with Negative Numbers)

The Pitfall: When shifting backward, we get negative values in our difference array. In many programming languages, the modulo operation with negative numbers doesn't behave as expected for circular wrapping.

For example, in Python:

  • -1 % 26 = 25 (works correctly)
  • But in languages like Java or C++: -1 % 26 = -1 (problematic!)

Incorrect Implementation:

# This might fail with large negative shifts new_pos = (original_pos + diff_array[i]) % 26 # Wrong for negative shifts!

If original_pos = 0 (letter 'a') and diff_array[i] = -30:

  • Without proper handling: (0 - 30) % 26 might give unexpected results in some languages

Correct Solution:

# Add an extra 26 (or multiple of 26) to ensure positive number before modulo new_pos = (original_pos + diff_array[i] + 26) % 26 # Works but might fail for very large negative shifts  # More robust solution for any negative shift size: new_pos = (original_pos + diff_array[i] % 26 + 26) % 26

2. Off-by-One Error in Difference Array Boundary

The Pitfall: Forgetting to update at end_idx + 1 or using wrong array size.

Incorrect Implementation:

# Wrong: Array too small diff_array = [0] * n # Should be n + 1  # Wrong: Incorrect boundary update diff_array[end_idx] -= direction # Should be end_idx + 1

This causes:

  • Array index out of bounds when end_idx = n - 1
  • Incorrect shift ranges (shifts bleeding into unwanted positions)

Correct Solution:

# Correct size and boundary diff_array = [0] * (n + 1) diff_array[end_idx + 1] -= direction

3. Forgetting to Handle the Direction Conversion

The Pitfall: Using the direction value directly without converting 0 to -1.

Incorrect Implementation:

# Wrong: Using direction as-is diff_array[start_idx] += direction # 0 means no shift instead of backward!

This causes backward shifts (direction = 0) to have no effect at all.

Correct Solution:

# Convert direction properly if direction == 0:  direction = -1 diff_array[start_idx] += direction

4. Integer Overflow in Accumulated Shifts

The Pitfall: With many overlapping shifts, the accumulated shift value can become very large.

Example Scenario:

# If we have 10,000 forward shifts on the same position # diff_array[i] could become 10,000 # This might cause issues in languages with fixed integer sizes

Correct Solution:

# Apply modulo during accumulation to keep numbers manageable for i in range(1, n + 1):  diff_array[i] = (diff_array[i] + diff_array[i - 1]) % 26

Or handle it during the final calculation:

# Take modulo of the shift amount first shift_amount = diff_array[i] % 26 new_pos = (original_pos + shift_amount + 26) % 26
Loading...
Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Tailor Your Study Plan:

What are the most two important steps in writing a depth first search function? (Select 2)

Recommended Readings

Prefix Sum

Prefix Sum Given an array of integers arr and a target value find a subarray that sums to the target Return the start and end indices of the subarray Input arr 1 20 3 30 5 4 target 7 Output 1 4 Explanation The subarray 20 3 30 from index 1 inclusive

Coding Interview Patterns: The Smart, Data-Driven Way to Prepare for Tech Interviews

Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way

Recursion Review

Recursion If you prefer videos here's a video that explains recursion in a fun and easy way Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https assets algo monster recursion jpg You first call Ben and ask him

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More