Shifting Letters

LeetCode 878 | Difficulty: Medium

Medium

Problem Description

You are given a string s of lowercase English letters and an integer array shifts of the same length.

Call the shift() of a letter, the next letter in the alphabet, (wrapping around so that 'z' becomes 'a').

- For example, `shift('a') = 'b'`, `shift('t') = 'u'`, and `shift('z') = 'a'`.

Now for each shifts[i] = x, we want to shift the first i + 1 letters of s, x times.

Return the final string after all such shifts to s are applied.

Example 1:

Input: s = "abc", shifts = [3,5,9]
Output: "rpl"
Explanation: 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"

Constraints:

- `1 <= s.length <= 10^5`

- `s` consists of lowercase English letters.

- `shifts.length == s.length`

- `0 <= shifts[i] <= 10^9`

Topics: Array, String, Prefix Sum

---

Approach

String Processing

Consider character frequency counts, two-pointer approaches, or building strings efficiently. For pattern matching, think about KMP or rolling hash. For palindromes, expand from center or use DP.

When to use

Anagram detection, palindrome checking, string transformation, pattern matching.

Prefix Sum

Build a prefix sum array where prefix[i] = sum of elements from index 0 to i. Then any subarray sum [l..r] = prefix[r] - prefix[l-1]. This turns range sum queries from O(n) to O(1).

When to use

Subarray sum queries, counting subarrays with a target sum, range computations.

---

Solutions

Solution 1: C# (Best: 382 ms)

Metric	Value
Runtime	382 ms
Memory	46.2 MB
Date	2022-02-02

Solution

public class Solution {
    public string ShiftingLetters(string s, int[] shifts) {
        int n = shifts.Length;
    for (int i = n-2; i >=0 ; i--)
    {
        shifts[i] = (shifts[i] + shifts[i+1])%26;       
    }
    char[] result = new char[n];
    for (int i = 0; i < n; i++)
    {
        result[i] = (char) (((s[i]-'a'+shifts[i])%26)+'a');
    }
    return new string(result);
    }
}

---

Complexity Analysis

Approach	Time	Space
Prefix Sum	$O(n)$	$O(n)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.