Shifting Letters II

Medium
1237.

Shifting Letters II

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

You are given a lowercase string s and a list of operations shifts, where shifts[i] = [start, end, direction].

Operation i shifts every character from index start to index end (inclusive) one step forward in the alphabet when direction == 1, or one step backward when direction == 0. The alphabet wraps around: shifting 'z' forward gives 'a' and shifting 'a' backward gives 'z'.

Apply all operations and return the final string.

Example 1

Input
s = "kairo", shifts = [[0,4,1],[1,2,0]]
Output
laisp
Explanation
The first operation gives `"lbjsp"`; the second moves indices 1 and 2 back, giving `"laisp"`.

Example 2

Input
s = "az", shifts = [[0,1,1]]
Output
ba
Explanation
`'z'` wraps around to `'a'`.

Example 3

Input
s = "a", shifts = [[0,0,0],[0,0,0]]
Output
y

Constraints

  • 1 <= s.length, shifts.length <= 5 * 10^4
  • shifts[i].length == 3
  • 0 <= start <= end < s.length
  • 0 <= direction <= 1
  • s consists of lowercase English letters
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 II — Solution in Python, Java & C++

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

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

  • Difficulty: Medium
  • Topics: Arrays, Strings, Prefix Sum
  • Asked at: Amazon, Google, Microsoft
  • 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 a list of operations shifts, where shifts[i] = [start, end, direction].

Operation i shifts every character from index start to index end (inclusive) one step forward in the alphabet when direction == 1, or one step backward when direction == 0. The alphabet wraps around: shifting 'z' forward gives 'a' and shifting 'a' backward gives 'z'.

Apply all operations and return the final string.

Example 1

Input: s = "kairo", shifts = [[0,4,1],[1,2,0]]
Output: laisp
Explanation: The first operation gives `"lbjsp"`; the second moves indices 1 and 2 back, giving `"laisp"`.

Example 2

Input: s = "az", shifts = [[0,1,1]]
Output: ba
Explanation: `'z'` wraps around to `'a'`.

Example 3

Input: s = "a", shifts = [[0,0,0],[0,0,0]]
Output: y

Constraints

  • 1 <= s.length, shifts.length <= 5 * 10^4
  • shifts[i].length == 3
  • 0 <= start <= end < s.length
  • 0 <= direction <= 1
  • s consists of lowercase English letters

Hints for Shifting Letters II

  1. Hint 1

    Applying each operation letter by letter is O(n·q). Only the net shift of each position matters.

  2. Hint 2

    Add +1 or -1 on a whole range at once with a difference array: mark the start, unmark just after the end.

  3. Hint 3

    A running sum over the difference array gives each position's net shift; reduce it modulo 26, taking care with negatives.

How to solve Shifting Letters II

The order of the operations does not matter, only each position's net shift. A difference array records every range update in O(1), and one prefix sum recovers the net shifts.

Approach

  1. Create diff of length n + 1, all zeros.
  2. For each [start, end, direction], let v = +1 if direction == 1 else -1; do diff[start] += v and diff[end + 1] -= v.
  3. Sweep i from 0 to n - 1 keeping a running sum cur += diff[i]; the new letter is (s[i] - 'a' + cur) mod 26, normalised into 0..25.

Why it works

Shifts commute, so the final letter at position i depends only on the sum of +1/-1 over the operations covering i. The running sum of the difference array at i counts exactly the operations whose range starts at or before i and has not ended before i, which are the ones covering it.

Complexity

  • Time — O(n + q)
  • Space — O(n)

Pitfalls

  • The net shift can be negative: use ((x % 26) + 26) % 26 in languages whose % keeps the sign.
  • diff needs one extra slot for end + 1 == n.
  • Backward is direction == 0, not -1.

Reference solution

Python

from typing import List

def shiftingLetters(s: str, shifts: List[List[int]]) -> str:
    n = len(s)
    diff = [0] * (n + 1)
    for a, b, d in shifts:
        v = 1 if d == 1 else -1
        diff[a] += v
        diff[b + 1] -= v
    out = []
    cur = 0
    for i, ch in enumerate(s):
        cur += diff[i]
        out.append(chr((ord(ch) - 97 + cur) % 26 + 97))
    return "".join(out)

Java

public static String shiftingLetters(String s, int[][] shifts) {
    int n = s.length();
    int[] diff = new int[n + 1];
    for (int[] sh : shifts) {
        int v = sh[2] == 1 ? 1 : -1;
        diff[sh[0]] += v;
        diff[sh[1] + 1] -= v;
    }
    char[] out = new char[n];
    int cur = 0;
    for (int i = 0; i < n; i++) {
        cur += diff[i];
        int x = (((s.charAt(i) - 'a' + cur) % 26) + 26) % 26;
        out[i] = (char) ('a' + x);
    }
    return new String(out);
}

C++

string shiftingLetters(string s, vector<vector<int>>& shifts) {
    int n = s.size();
    vector<int> diff(n + 1, 0);
    for (auto& sh : shifts) {
        int v = sh[2] == 1 ? 1 : -1;
        diff[sh[0]] += v;
        diff[sh[1] + 1] -= v;
    }
    int cur = 0;
    for (int i = 0; i < n; i++) {
        cur += diff[i];
        int x = (((s[i] - 'a' + cur) % 26) + 26) % 26;
        s[i] = (char)('a' + x);
    }
    return s;
}

JavaScript

var shiftingLetters = function(s, shifts) {
    var n = s.length;
    var diff = new Array(n + 1).fill(0);
    for (var i = 0; i < shifts.length; i++) {
        var v = shifts[i][2] === 1 ? 1 : -1;
        diff[shifts[i][0]] += v;
        diff[shifts[i][1] + 1] -= v;
    }
    var out = [], cur = 0;
    for (var j = 0; j < n; j++) {
        cur += diff[j];
        var x = (((s.charCodeAt(j) - 97 + cur) % 26) + 26) % 26;
        out.push(String.fromCharCode(97 + x));
    }
    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