LeetCode 2381 - Shifting Letters II

This problem gives us a lowercase English string s and a list of shift operations. Each operation is represented as: The operation affects every character from index start to index end, inclusive.

leetcodemediumarraystringprefix-sum

LeetCode Problem 2381

Difficulty: 🟡 Medium
Topics: Array, String, Prefix Sum

Solution

LeetCode 2381 - Shifting Letters II

Problem Understanding

This problem gives us a lowercase English string s and a list of shift operations. Each operation is represented as:

[start, end, direction]

The operation affects every character from index start to index end, inclusive.

If direction == 1, every character in that range is shifted forward by one letter in the alphabet:

a -> b
b -> c
...
z -> a

If direction == 0, every character is shifted backward:

b -> a
a -> z

The goal is to apply all operations and return the final transformed string.

The important detail is that multiple operations may overlap. A character can be shifted many times, both forward and backward. Instead of applying each operation immediately, we need to determine the total net shift for every position.

The constraints are large:

  • s.length <= 5 * 10^4
  • shifts.length <= 5 * 10^4

A naive solution that updates every character for every operation could require:

5 * 10^4 * 5 * 10^4 = 2.5 * 10^9

operations in the worst case, which is far too slow.

The input guarantees:

  • All indices are valid.
  • The string contains only lowercase English letters.
  • Every shift direction is either forward or backward.

Several edge cases are important:

  • Operations may overlap heavily.
  • A character may be shifted many times in both directions.
  • Large cumulative shifts must wrap correctly using modulo 26.
  • Single-character ranges like [3,3,1] must work correctly.
  • Backward shifts can create negative totals, so modulo handling must be careful.

Approaches

Brute Force Approach

The most direct solution is to simulate every operation exactly as described.

For each shift operation:

  1. Read start, end, and direction.
  2. Iterate through every index from start to end.
  3. Shift the corresponding character forward or backward by one.

This approach is correct because it literally follows the problem statement.

However, it is inefficient. If every operation affects almost the entire string, then each operation costs O(n). With up to 5 * 10^4 operations, the total complexity becomes O(n * m) where:

  • n = len(s)
  • m = len(shifts)

That worst-case runtime is too large.

Optimal Approach, Prefix Sum / Difference Array

The key observation is that we do not actually need to update characters during every operation.

Instead, we only need to know the final net shift applied to each index.

For example:

+1
-1
+1

on the same character results in a total shift of +1.

This turns the problem into a range update problem.

A difference array allows us to apply range increments efficiently:

  • Add +1 at the start of a forward range.
  • Add -1 at the start of a backward range.
  • Subtract the same value immediately after the range ends.

Later, a prefix sum reconstructs the actual cumulative shift at every position.

This reduces each operation from O(length of range) to O(1).

Approach Time Complexity Space Complexity Notes
Brute Force O(n * m) O(1) Simulates every shift directly
Optimal O(n + m) O(n) Uses difference array and prefix sums

Algorithm Walkthrough

  1. Create a difference array of size n + 1, initialized with zeros.

The extra slot helps us mark where a range effect stops. 2. Process every shift operation.

For each operation:

  • Convert the direction into a value:

  • 1 -> +1

  • 0 -> -1

  • Add this value at start.

  • Subtract this value at end + 1 if it exists.

This records the range effect without updating every element individually. 3. Compute the prefix sum while traversing the string.

The running prefix sum represents the total shift affecting the current index. 4. Convert each character into its alphabet index.

For example:

a -> 0
b -> 1
...
z -> 25
  1. Apply the cumulative shift.

Use modulo 26 to wrap around the alphabet correctly. 6. Convert the shifted value back into a character. 7. Build and return the final string.

Why it works

The difference array records how shifts begin and end across ranges. When we compute the prefix sum, every position accumulates exactly the contributions from all ranges covering that index. Therefore, the computed cumulative shift for each character matches the result of applying every operation individually. Since modulo 26 correctly handles alphabet wrapping, the final string is guaranteed to be correct.

Python Solution

from typing import List

class Solution:
    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:
        n = len(s)
        
        # Difference array
        diff = [0] * (n + 1)
        
        # Apply range updates
        for start, end, direction in shifts:
            shift_value = 1 if direction == 1 else -1
            
            diff[start] += shift_value
            
            if end + 1 < len(diff):
                diff[end + 1] -= shift_value
        
        result = []
        current_shift = 0
        
        # Build final string using prefix sums
        for i in range(n):
            current_shift += diff[i]
            
            original_position = ord(s[i]) - ord('a')
            
            shifted_position = (original_position + current_shift) % 26
            
            shifted_character = chr(shifted_position + ord('a'))
            
            result.append(shifted_character)
        
        return "".join(result)

The implementation starts by creating a difference array named diff. This array tracks how shifts change across ranges instead of modifying characters directly.

For each operation:

[start, end, direction]

the code converts the direction into either +1 or -1.

The update:

diff[start] += shift_value

marks where the shift begins.

The update:

diff[end + 1] -= shift_value

marks where the shift stops affecting future positions.

After all operations are processed, the algorithm traverses the string once while maintaining a running prefix sum in current_shift. This value represents the total net shift for the current character.

Each character is converted into a numeric alphabet index using:

ord(s[i]) - ord('a')

The shift is applied using modulo 26 so wrapping works correctly for both positive and negative shifts.

Finally, the transformed characters are joined into the answer string.

Go Solution

func shiftingLetters(s string, shifts [][]int) string {
	n := len(s)

	// Difference array
	diff := make([]int, n+1)

	// Apply range updates
	for _, shift := range shifts {
		start := shift[0]
		end := shift[1]
		direction := shift[2]

		shiftValue := -1
		if direction == 1 {
			shiftValue = 1
		}

		diff[start] += shiftValue

		if end+1 < len(diff) {
			diff[end+1] -= shiftValue
		}
	}

	result := []byte(s)

	currentShift := 0

	// Build final string
	for i := 0; i < n; i++ {
		currentShift += diff[i]

		originalPosition := int(result[i] - 'a')

		shiftedPosition := (originalPosition + currentShift) % 26

		// Handle negative modulo
		if shiftedPosition < 0 {
			shiftedPosition += 26
		}

		result[i] = byte(shiftedPosition) + 'a'
	}

	return string(result)
}

The Go implementation follows the same algorithm as the Python version.

One important Go-specific detail is modulo handling. In Python:

(-1) % 26 == 25

but in Go:

-1 % 26 == -1

Therefore, the Go solution explicitly adjusts negative values:

if shiftedPosition < 0 {
    shiftedPosition += 26
}

The solution also uses a []byte slice for efficient in-place character updates since Go strings are immutable.

Worked Examples

Example 1

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

Step 1: Initialize Difference Array

n = 3

diff = [0, 0, 0, 0]

Step 2: Apply Operations

Operation 1

[0,1,0]
direction = backward = -1

Update:

diff[0] += -1
diff[2] -= -1

Result:

diff = [-1, 0, 1, 0]

Operation 2

[1,2,1]
direction = forward = +1

Update:

diff[1] += 1
diff[3] -= 1

Result:

diff = [-1, 1, 1, -1]

Operation 3

[0,2,1]
direction = forward = +1

Update:

diff[0] += 1
diff[3] -= 1

Result:

diff = [0, 1, 1, -2]

Step 3: Prefix Sum and Character Updates

Index Character Running Shift Shifted Character
0 a 0 a
1 b 1 c
2 c 2 e

Final result:

"ace"

Example 2

s = "dztz"
shifts = [[0,0,0],[1,1,1]]

Step 1: Initialize Difference Array

diff = [0, 0, 0, 0, 0]

Step 2: Apply Operations

Operation 1

[0,0,0]
direction = -1

Update:

diff[0] += -1
diff[1] -= -1

Result:

diff = [-1, 1, 0, 0, 0]

Operation 2

[1,1,1]
direction = +1

Update:

diff[1] += 1
diff[2] -= 1

Result:

diff = [-1, 2, -1, 0, 0]

Step 3: Prefix Sum

Index Character Running Shift Shifted Character
0 d -1 c
1 z 1 a
2 t 0 t
3 z 0 z

Final result:

"catz"

Complexity Analysis

Measure Complexity Explanation
Time O(n + m) Each shift operation and each character is processed once
Space O(n) The difference array requires linear extra space

The algorithm processes every shift operation in constant time using the difference array technique. Then it performs one linear traversal of the string to compute prefix sums and build the final answer. Since there are no nested loops over ranges, the solution scales efficiently to the maximum constraints.

Test Cases

from typing import List

class Solution:
    def shiftingLetters(self, s: str, shifts: List[List[int]]) -> str:
        n = len(s)

        diff = [0] * (n + 1)

        for start, end, direction in shifts:
            shift_value = 1 if direction == 1 else -1

            diff[start] += shift_value

            if end + 1 < len(diff):
                diff[end + 1] -= shift_value

        result = []
        current_shift = 0

        for i in range(n):
            current_shift += diff[i]

            new_pos = (ord(s[i]) - ord('a') + current_shift) % 26

            result.append(chr(new_pos + ord('a')))

        return "".join(result)

solution = Solution()

# Provided examples
assert solution.shiftingLetters(
    "abc",
    [[0,1,0],[1,2,1],[0,2,1]]
) == "ace"  # example 1

assert solution.shiftingLetters(
    "dztz",
    [[0,0,0],[1,1,1]]
) == "catz"  # example 2

# Single character forward wrap
assert solution.shiftingLetters(
    "z",
    [[0,0,1]]
) == "a"  # z wraps to a

# Single character backward wrap
assert solution.shiftingLetters(
    "a",
    [[0,0,0]]
) == "z"  # a wraps to z

# Multiple overlapping forward shifts
assert solution.shiftingLetters(
    "aaa",
    [[0,2,1],[0,2,1],[0,2,1]]
) == "ddd"  # cumulative positive shifts

# Multiple overlapping backward shifts
assert solution.shiftingLetters(
    "ddd",
    [[0,2,0],[0,2,0]]
) == "bbb"  # cumulative negative shifts

# Mixed overlapping operations
assert solution.shiftingLetters(
    "abcde",
    [[0,2,1],[1,4,0],[2,3,1]]
) == "bbcdf"  # mixed directions

# No net shift
assert solution.shiftingLetters(
    "leetcode",
    [[0,7,1],[0,7,0]]
) == "leetcode"  # shifts cancel out

# Large shift accumulation
assert solution.shiftingLetters(
    "a",
    [[0,0,1]] * 52
) == "a"  # 52 shifts equals two full rotations

# Edge range updates
assert solution.shiftingLetters(
    "xyz",
    [[0,2,1]]
) == "yza"  # full string update
Test Why
Example 1 Validates overlapping forward and backward operations
Example 2 Validates single-index updates
"z" forward Tests forward alphabet wrapping
"a" backward Tests backward alphabet wrapping
Multiple forward overlaps Verifies cumulative positive shifts
Multiple backward overlaps Verifies cumulative negative shifts
Mixed overlaps Tests correctness with intersecting ranges
Net zero shift Ensures opposite operations cancel properly
Large shift accumulation Verifies modulo 26 behavior
Full-range update Tests updates spanning entire string

Edge Cases

Large Negative Shifts

A character may receive many backward shifts, causing the cumulative shift value to become highly negative. This can create bugs if modulo arithmetic is handled incorrectly.

For example:

"a" shifted backward 27 times

should become:

"z"

The implementation handles this safely using modulo 26 arithmetic. Python automatically converts negative modulo results into positive equivalents.

Full String Range Updates

An operation may affect the entire string:

[0, n - 1, 1]

This is important because updating end + 1 must not access an invalid index.

The implementation avoids out-of-bounds errors by checking:

if end + 1 < len(diff):

before subtracting from the difference array.

Heavy Overlapping Operations

Many operations may overlap on the same indices. A naive implementation would repeatedly update the same characters, causing severe performance issues.

The difference array approach handles overlapping efficiently because every operation only performs two constant-time updates, regardless of range size. The prefix sum naturally combines all overlapping effects into the final cumulative shift for each position.