Problem

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.

Examples

Example 1

1
2
3
4
5
6

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

1
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

Solution

Method 1 – Prefix Sum from Right

Intuition

To efficiently apply multiple overlapping shifts, we can process the shifts array from right to left, accumulating the total shifts needed for each character. This way, each character is shifted by the sum of all relevant shifts, avoiding repeated work.

Approach

  1. Initialize a variable total to 0 to keep track of cumulative shifts.
  2. Iterate from the end of the shifts array to the start:
  • Add shifts[i] to total.
  • For each character s[i], shift it by total % 26 positions.
  • Store the shifted character in the answer.
  1. Join and return the final shifted string.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
public:
   string shiftingLetters(string s, vector<int>& shifts) {
      int n = s.size();
      vector<char> ans(n);
      long long total = 0;
      for (int i = n - 1; i >= 0; --i) {
        total = (total + shifts[i]) % 26;
        ans[i] = 'a' + (s[i] - 'a' + total) % 26;
      }
      return string(ans.begin(), ans.end());
   }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

func shiftingLetters(s string, shifts []int) string {
   n := len(s)
   ans := make([]byte, n)
   total := 0
   for i := n - 1; i >= 0; i-- {
      total = (total + shifts[i]) % 26
      ans[i] = byte('a' + (int(s[i]-'a')+total)%26)
   }
   return string(ans)
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
   public String shiftingLetters(String s, int[] shifts) {
      int n = s.length();
      char[] ans = new char[n];
      long total = 0;
      for (int i = n - 1; i >= 0; --i) {
        total = (total + shifts[i]) % 26;
        ans[i] = (char)('a' + (s.charAt(i) - 'a' + (int)total) % 26);
      }
      return new String(ans);
   }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
   fun shiftingLetters(s: String, shifts: IntArray): String {
      val n = s.length
      val ans = CharArray(n)
      var total = 0L
      for (i in n - 1 downTo 0) {
        total = (total + shifts[i]) % 26
        ans[i] = 'a' + ((s[i] - 'a' + total.toInt()) % 26)
      }
      return String(ans)
   }
}
1
2
3
4
5
6
7
8
9

class Solution:
   def shiftingLetters(self, s: str, shifts: list[int]) -> str:
      n = len(s)
      ans: list[str] = [''] * n
      total: int = 0
      for i in range(n - 1, -1, -1):
        total = (total + shifts[i]) % 26
        ans[i] = chr((ord(s[i]) - ord('a') + total) % 26 + ord('a'))
      return ''.join(ans)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

impl Solution {
   pub fn shifting_letters(s: String, shifts: Vec<i32>) -> String {
      let n = s.len();
      let mut ans = vec!['a'; n];
      let mut total = 0i64;
      let s_bytes = s.as_bytes();
      for i in (0..n).rev() {
        total = (total + shifts[i] as i64) % 26;
        ans[i] = ((s_bytes[i] - b'a' + total as u8) % 26 + b'a') as char;
      }
      ans.into_iter().collect()
   }
}

Complexity

  • ⏰ Time complexity: O(n) — Single pass through the string and shifts.
  • 🧺 Space complexity: O(n) — For the answer array.