Shifting Letters

Medium
1746.

Shifting Letters

Shifting Letters is a medium coding problem on arrays, strings and prefix sum, asked in Amazon and Google interviews.

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

Shifting a letter moves it to the next letter of the alphabet, wrapping around so that 'z' becomes 'a'. For every i, shift the first i + 1 letters of s by shifts[i] positions.

Return the string after all the shifts have been applied.

Example 1

Input
s = "kai", shifts = [1,2,3]
Output
qfl
Explanation
Letter 0 is shifted 1 + 2 + 3 = 6 times, letter 1 is shifted 2 + 3 = 5 times, letter 2 is shifted 3 times.

Example 2

Input
s = "zz", shifts = [1,26]
Output
az
Explanation
The first `z` moves 27 positions — one full lap plus one.

Example 3

Input
s = "a", shifts = [1000000000]
Output
m
Explanation
10^9 leaves remainder 12 when divided by 26.

Constraints

  • 1 <= s.length <= 10^5
  • s consists of lowercase English letters
  • shifts.length == s.length
  • 0 <= shifts[i] <= 10^9
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @param {number[]} shifts
 * @return {string}
 */
var shiftingLetters = function(s, shifts) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Shifting Letters — Solution in Python, Java & C++

Shifting Letters solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem on arrays and strings.

Shifting Letters is a medium coding problem on arrays, strings and prefix sum, asked in Amazon and Google interviews.

  • Difficulty: Medium
  • Topics: Arrays, Strings, Prefix Sum
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

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

Shifting a letter moves it to the next letter of the alphabet, wrapping around so that 'z' becomes 'a'. For every i, shift the first i + 1 letters of s by shifts[i] positions.

Return the string after all the shifts have been applied.

Example 1

Input: s = "kai", shifts = [1,2,3]
Output: qfl
Explanation: Letter 0 is shifted 1 + 2 + 3 = 6 times, letter 1 is shifted 2 + 3 = 5 times, letter 2 is shifted 3 times.

Example 2

Input: s = "zz", shifts = [1,26]
Output: az
Explanation: The first `z` moves 27 positions — one full lap plus one.

Example 3

Input: s = "a", shifts = [1000000000]
Output: m
Explanation: 10^9 leaves remainder 12 when divided by 26.

Constraints

  • 1 <= s.length <= 10^5
  • s consists of lowercase English letters
  • shifts.length == s.length
  • 0 <= shifts[i] <= 10^9

Hints for Shifting Letters

  1. Hint 1

    Letter i is affected by shifts[i], shifts[i + 1], …, shifts[n - 1] — every shift whose prefix covers it.

  2. Hint 2

    So letter i moves by the suffix sum of shifts starting at i. Walk from the right to build it in one pass.

  3. Hint 3

    The sums can reach 10^14, but only their value modulo 26 matters — reduce as you go.

How to solve Shifting Letters

The total shift applied to position i is shifts[i] + shifts[i + 1] + … + shifts[n - 1], so one right-to-left pass keeping a running sum modulo 26 shifts every letter.

Approach

  1. Set total = 0.
  2. For i from n - 1 down to 0: total = (total + shifts[i]) mod 26, then replace s[i] with the letter (s[i] - 'a' + total) mod 26 places after 'a'.
  3. Return the rebuilt string.

Why it works

The operation for index j touches letters 0..j, so letter i receives exactly the shifts with j >= i. Shifting by x and by x mod 26 land on the same letter because the alphabet wraps every 26 steps.

Complexity

  • Time — O(n)
  • Space — O(n) for the output string

Pitfalls

  • Without the modulo the running sum overflows 32-bit integers (10^5 · 10^9).
  • Shifting prefixes one by one is O(n^2) and too slow for n = 10^5.

Reference solution

Python

from typing import List

def shiftingLetters(s: str, shifts: List[int]) -> str:
    out = list(s)
    total = 0
    for i in range(len(s) - 1, -1, -1):
        total = (total + shifts[i]) % 26
        out[i] = chr(97 + (ord(s[i]) - 97 + total) % 26)
    return "".join(out)

Java

public static String shiftingLetters(String s, int[] shifts) {
    char[] out = s.toCharArray();
    int total = 0;
    for (int i = out.length - 1; i >= 0; i--) {
        total = (total + shifts[i] % 26) % 26;
        out[i] = (char) ('a' + (out[i] - 'a' + total) % 26);
    }
    return new String(out);
}

C++

string shiftingLetters(string s, vector<int>& shifts) {
    int total = 0;
    for (int i = (int) s.size() - 1; i >= 0; i--) {
        total = (total + shifts[i] % 26) % 26;
        s[i] = (char) ('a' + (s[i] - 'a' + total) % 26);
    }
    return s;
}

JavaScript

var shiftingLetters = function(s, shifts) {
    var out = new Array(s.length);
    var total = 0;
    for (var i = s.length - 1; i >= 0; i--) {
        total = (total + shifts[i]) % 26;
        out[i] = String.fromCharCode(97 + (s.charCodeAt(i) - 97 + total) % 26);
    }
    return out.join("");
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Strings