Shifting Letters II

Problem (restated)

String s of lowercase letters. shifts[i]=[start,end,dir] shifts inclusive range forward (dir=1) or backward (dir=0) by 1. Return final string.

Intuition

Net shift per index via difference array; apply mod 26 to each character.

Approaches

export function shiftingLetters(s: string, shifts: number[][]): string {
  const n = s.length;
  const diff = Array(n + 1).fill(0);
  for (const sh of shifts) {
    const d = sh[2] === 1 ? 1 : -1;
    diff[sh[0]!] += d;
    diff[sh[1]! + 1] -= d;
  }
  const chars = s.split("");
  let cur = 0;
  for (let i = 0; i < n; i++) {
    cur += diff[i]!;
    let k = (chars[i]!.charCodeAt(0) - 97 + cur) % 26;
    if (k < 0) k += 26;
    chars[i] = String.fromCharCode(97 + k);
  }
  return chars.join("");
}

export function shiftingLetters(s: string, shifts: number[][]): string {
  const n = s.length;
  const diff = Array(n + 1).fill(0);
  for (const sh of shifts) {
    const d = sh[2] === 1 ? 1 : -1;
    diff[sh[0]!] += d;
    diff[sh[1]! + 1] -= d;
  }
  const chars = s.split("");
  let cur = 0;
  for (let i = 0; i < n; i++) {
    cur += diff[i]!;
    let k = (chars[i]!.charCodeAt(0) - 97 + cur) % 26;
    if (k < 0) k += 26;
    chars[i] = String.fromCharCode(97 + k);
  }
  return chars.join("");
}

Template connection

Difference array range updates on a string.

Reflection

• Each shift is +1 or −1 on a range. The final prefix is taken mod 26. Is end inclusive?
• A backward shift goes negative. Do Python % and C# % produce the same remainder?
• No shifts: the string stays put. Overlapping ranges add up in the prefix.