LeetCode 848 - Shifting Letters

This problem asks us to repeatedly apply character shifts to a string of lowercase English letters. We are given two inputs: - A string s, consisting only of lowercase English letters.

leetcodemediumarraystringprefix-sum

LeetCode Problem 848

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

Solution

Problem Understanding

This problem asks us to repeatedly apply character shifts to a string of lowercase English letters.

We are given two inputs:

  • A string s, consisting only of lowercase English letters.
  • An integer array shifts, where shifts[i] tells us how many times we should shift the first i + 1 characters of the string.

A single shift means moving a character to the next alphabet letter, wrapping around from 'z' back to 'a'.

For example:

  • 'a' → 'b'
  • 'c' → 'd'
  • 'z' → 'a'

The key detail is that every operation affects a prefix of the string. If shifts[i] = x, then the first i + 1 characters are shifted x times.

We must return the final string after all operations have been applied.

At first glance, this looks like a simulation problem where we repeatedly modify prefixes. However, the constraints reveal why that approach is dangerous.

The length of the string can be as large as 10^5, and each shift value can be as large as 10^9.

This tells us two important things:

  1. We cannot literally perform shifts one by one because 10^9 operations per character would be impossible.
  2. We cannot repeatedly modify prefixes in an O(n²) way because n = 10^5 would make that too slow.

Instead, we need a way to efficiently determine how many total shifts each character receives.

Important Observations

A character at index i is affected by all operations from index i to the end.

For example:

s = "abc"
shifts = [3,5,9]

Character 'a' at index 0 gets shifted:

3 + 5 + 9 = 17 times

Character 'b' at index 1 gets shifted:

5 + 9 = 14 times

Character 'c' at index 2 gets shifted:

9 times

This means we need a suffix sum, not repeated prefix updates.

Edge Cases

A few cases can easily trip up a naive implementation.

If the string has length 1, the algorithm should still work correctly because only one character is shifted.

Very large shift values such as 10^9 require modular arithmetic. Since the alphabet only has 26 letters, shifting 26 times returns to the same character. Therefore, we only care about:

shift % 26

Strings containing 'z' require wraparound handling. For example, shifting 'z' by 1 should become 'a', not an invalid character.

The problem guarantees:

  • s contains only lowercase English letters.
  • shifts.length == s.length
  • s.length >= 1

So we do not need to handle invalid input or mismatched lengths.

Approaches

Brute Force Approach

The most straightforward approach is to simulate the problem exactly as described.

For each index i:

  1. Take shifts[i].
  2. Shift the first i + 1 characters that many times.
  3. Continue to the next operation.

To avoid repeated single-character shifting, we could compute:

effective_shift = shifts[i] % 26

and apply that directly to every character in the prefix.

Although this produces the correct answer, it is far too slow.

For every i, we modify up to i + 1 characters.

The total work becomes:

1 + 2 + 3 + ... + n = O(n²)

With n = 10^5, this would be far too expensive.

Key Insight

Instead of repeatedly shifting prefixes, we can ask:

How many total shifts does each character receive?

A character at position i is affected by every shift operation from i onward.

That means:

total_shift[i] =
shifts[i] + shifts[i+1] + ... + shifts[n-1]

This is a suffix sum problem.

We can process the array from right to left while maintaining a running total of shifts.

For each character:

  1. Add the current shift value to a running suffix sum.
  2. Reduce it modulo 26.
  3. Apply that shift to the current character.

This avoids repeatedly touching prefixes and reduces the complexity to linear time.

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(n) Repeatedly updates prefixes
Optimal O(n) O(n) Uses suffix sum of shifts

Algorithm Walkthrough

  1. Convert the string into a mutable list of characters.

Strings in Python are immutable, so modifying characters directly is inefficient. Converting to a list allows in-place updates. 2. Initialize a running suffix sum.

We keep a variable called total_shift that stores the cumulative shifts affecting the current character. 3. Traverse the string from right to left.

We go backward because each position depends on all future shift values. 4. Update the running shift total.

Add:

shifts[i]

to total_shift.

Since shifting by 26 changes nothing, reduce the result:

total_shift %= 26
  1. Convert the current character into a number.

We map:

'a' → 0
'b' → 1
...
'z' → 25

using ASCII arithmetic. 6. Apply the shift.

Compute:

new_position =
(old_position + total_shift) % 26

The modulo handles alphabet wraparound. 7. Convert back into a character.

Turn the shifted numeric value back into a lowercase letter. 8. Join the character list into a string.

Return the final transformed string.

Why it works

The core invariant is that when processing index i, total_shift contains the sum of all shift operations affecting character i.

Because every operation at index j ≥ i affects character i, traversing from right to left guarantees we accumulate exactly the shifts that apply to the current character. Applying modulo 26 preserves correctness because the alphabet repeats every 26 shifts.

Python Solution

from typing import List

class Solution:
    def shiftingLetters(self, s: str, shifts: List[int]) -> str:
        characters = list(s)
        total_shift = 0

        for i in range(len(s) - 1, -1, -1):
            total_shift = (total_shift + shifts[i]) % 26

            current_position = ord(characters[i]) - ord('a')
            new_position = (current_position + total_shift) % 26

            characters[i] = chr(new_position + ord('a'))

        return ''.join(characters)

The implementation begins by converting the input string into a list of characters because strings in Python cannot be modified in place.

We maintain total_shift, which stores the cumulative suffix shift affecting the current character. By iterating from right to left, we naturally build the suffix sum as we go.

For each character, we convert it into a numeric alphabet index using ASCII subtraction. After applying the shift with modulo 26, we convert the result back into a character and overwrite the original position.

Finally, we join the list back into a string and return the result.

Go Solution

func shiftingLetters(s string, shifts []int) string {
	chars := []byte(s)
	totalShift := 0

	for i := len(s) - 1; i >= 0; i-- {
		totalShift = (totalShift + shifts[i]) % 26

		currentPosition := int(chars[i] - 'a')
		newPosition := (currentPosition + totalShift) % 26

		chars[i] = byte(newPosition) + 'a'
	}

	return string(chars)
}

The Go implementation follows the same logic but uses a []byte slice because strings in Go are immutable.

One important Go-specific detail is type conversion. Since bytes are unsigned integers, arithmetic involving characters must be converted to int before applying modulo operations.

Overflow is not an issue because we continuously reduce the cumulative shift using % 26, keeping values very small.

Worked Examples

Example 1

s = "abc"
shifts = [3,5,9]

We process from right to left.

Index Character Shift Added Running Shift New Character
2 c 9 9 l
1 b 5 14 p
0 a 3 17 r

Final result:

"rpl"

Example 2

s = "aaa"
shifts = [1,2,3]
Index Character Shift Added Running Shift New Character
2 a 3 3 d
1 a 2 5 f
0 a 1 6 g

Final result:

"gfd"

Complexity Analysis

Measure Complexity Explanation
Time O(n) Single pass through the string
Space O(n) Mutable character array for output

The algorithm processes each character exactly once while maintaining only a running shift total. Since every operation inside the loop takes constant time, the overall time complexity is linear.

The extra space comes from converting the string into a mutable character array. Aside from that, only a few scalar variables are used.

Test Cases

sol = Solution()

assert sol.shiftingLetters("abc", [3, 5, 9]) == "rpl"  # Example 1
assert sol.shiftingLetters("aaa", [1, 2, 3]) == "gfd"  # Example 2

assert sol.shiftingLetters("a", [0]) == "a"  # Single character, no shift
assert sol.shiftingLetters("z", [1]) == "a"  # Wraparound from z to a
assert sol.shiftingLetters("z", [26]) == "z"  # Full alphabet cycle
assert sol.shiftingLetters("abc", [0, 0, 0]) == "abc"  # No shifts

assert sol.shiftingLetters("zzz", [1, 1, 1]) == "cba"  # Multiple wraparounds
assert sol.shiftingLetters("aaa", [1000000000, 1000000000, 1000000000]) == "mie"  # Very large shifts

assert sol.shiftingLetters("abcde", [1, 2, 3, 4, 5]) == "ppomj"  # Increasing shifts
assert sol.shiftingLetters("leetcode", [0] * 8) == "leetcode"  # All zero shifts
Test Why
("abc", [3,5,9]) Validates provided example
("aaa", [1,2,3]) Validates cumulative suffix behavior
("a", [0]) Minimum input size
("z", [1]) Ensures alphabet wraparound
("z", [26]) Verifies modulo behavior
("abc", [0,0,0]) No-op scenario
("zzz", [1,1,1]) Multiple wraparounds
Large 10^9 shifts Ensures modulo optimization works
Increasing shifts Tests suffix accumulation correctness
Zero shifts on longer string Confirms unchanged output

Edge Cases

A string of length 1 is an important boundary condition. Since there is only one character, only one shift operation applies. A buggy implementation might accidentally mishandle indexing when traversing backward. This solution correctly processes index 0 and returns the shifted result.

Very large shift values can be problematic if handled literally. Since shifts[i] can be as large as 10^9, repeatedly shifting characters one step at a time would be impossibly slow. The implementation avoids this by reducing cumulative shifts modulo 26, because every 26 shifts cycle back to the original character.

Characters near the end of the alphabet, especially 'z', require proper wraparound logic. Without modulo arithmetic, shifting 'z' by 1 could produce invalid characters. By computing:

(current_position + total_shift) % 26

the implementation correctly maps values back into the valid alphabet range.