#848

Medium

LeetCode Problem Workspace

Shifting Letters

Given a string and a shift array, shift the first i+1 letters of the string as specified in the array.

Problem Statement

You are given a string s consisting of lowercase English letters and an integer array shifts, both of length n. For each index i in the array, you need to shift the first i + 1 letters of the string by shifts[i] positions. The shift operation wraps around the alphabet, meaning that 'z' becomes 'a'.

After applying the shifts as described, return the modified string. The problem can be solved using array manipulation and string transformation, ensuring that the shifts are applied efficiently by leveraging prefix sums to minimize repetitive work.

Examples

Example 1

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

Output: "rpl"

We start with "abc". After shifting the first 1 letters of s by 3, we have "dbc". After shifting the first 2 letters of s by 5, we have "igc". After shifting the first 3 letters of s by 9, we have "rpl", the answer.

Example 2

Input: s = "aaa", shifts = [1,2,3]

Output: "gfd"

Example details omitted.

Constraints

1 <= s.length <= 105
s consists of lowercase English letters.
shifts.length == s.length
0 <= shifts[i] <= 109

Solution Approach

Prefix Sum Calculation

Start by calculating the cumulative shifts using a prefix sum approach. This allows you to compute the total shifts needed for each letter efficiently without redundant calculations.

Modulo Operation for Shifts

Since the alphabet is cyclic, use the modulo operation to ensure that the shift does not exceed the bounds of 'a' to 'z'. The modulo operation will wrap around the shifts that go beyond 26 letters.

Apply Shifts to String

Iterate over the string and apply the cumulative shift to each character. After applying the shift, adjust the character accordingly using the modulo operation to handle the wrap-around from 'z' to 'a'.

Complexity Analysis

Metric	Value
Time	O(N)
Space	O(N)

The time complexity of this approach is O(N), where N is the length of the string, due to the linear pass to compute the prefix sum and apply the shifts. The space complexity is O(N) because we store the prefix sums and the resulting shifted string.

What Interviewers Usually Probe

Look for understanding of how to efficiently handle repeated shifts using a prefix sum.
Evaluate the candidate's ability to handle string transformations and modulo operations.
Check how well the candidate can apply optimizations to avoid unnecessary recomputations.

Common Pitfalls or Variants

Common pitfalls

Misunderstanding the shift operation by not properly wrapping around the alphabet.
Failing to efficiently calculate shifts by not using a prefix sum or cumulative sum approach.
Ignoring the modulo operation for large shift values that exceed 26, leading to incorrect results.

Follow-up variants

Changing the alphabet to a different set of characters (e.g., uppercase letters or custom characters).
Introducing a variation where shifts are applied in reverse order (i.e., starting from the last element of the array).
Handling larger shift values more efficiently by implementing a custom modulo-based transformation.

FAQ

What is the time complexity of the Shifting Letters problem?

The time complexity is O(N), where N is the length of the string, as we perform a linear scan to compute prefix sums and apply the shifts.

How do I handle large shift values in the Shifting Letters problem?

Use the modulo operation to ensure that shifts greater than 26 wrap around correctly, preventing invalid character shifts.

What is the key concept to solve the Shifting Letters problem efficiently?

The key concept is to use a prefix sum approach to calculate cumulative shifts, combined with modulo arithmetic for wrap-around behavior in the alphabet.

Can the Shifting Letters problem be solved in constant space?

No, the problem requires O(N) space due to the need to store the shift values and the resulting string.

What is the best approach for applying the shifts to the string in Shifting Letters?

Iterate through the string and apply the cumulative shifts using modulo to ensure that each character wraps around correctly after a shift.

terminal

Solution

Solution 1: Suffix Sum

For each character in the string $s$, we need to calculate its final shift amount, which is the sum of $\textit{shifts}[i]$, $\textit{shifts}[i + 1]$, $\textit{shifts}[i + 2]$, and so on. We can use the concept of suffix sum, traversing $\textit{shifts}$ from back to front, calculating the final shift amount for each character, and then taking modulo $26$ to get the final character.

1

2

3

4

5

6

7

8

9

class Solution:
    def shiftingLetters(self, s: str, shifts: List[int]) -> str:
        n, t = len(s), 0
        s = list(s)
        for i in range(n - 1, -1, -1):
            t += shifts[i]
            j = (ord(s[i]) - ord('a') + t) % 26
            s[i] = ascii_lowercase[j]
        return ''.join(s)

Continue Practicing

#1177 can make palindrome from substring #1769 minimum number of operations to move all balls to each box #843 guess the word