2381. Shifting Letters II

Time: O(n + m)

Space: O(n)

Intuition

Apply shift operations to string. Optimize: each operation [direction, amount] shifts a range. Use difference array for net shifts.

Algorithm

1diff array of size n+1. For each [dir, amt, l, r]: diff[l] += shift, diff[r+1] -= shift.
2Prefix sum to get net shift per position. Apply modulo 26.

Common Pitfalls

•Net shift can be negative; use ((shift % 26) + 26) % 26. Difference array + prefix sum = O(n+q).

2381.cs

// Approach: Difference array on timeline; prefix sum gives cumulative shift at each index.
// Time: O(n + m) Space: O(n)

public class Solution
{
    public string ShiftingLetters(string s, int[][] shifts)
    {
        StringBuilder sb = new StringBuilder();
        int currShift = 0;
        int[] timeline = new int[s.Length + 1];

        foreach (var shift in shifts)
        {
            int start = shift[0];
            int end = shift[1];
            int direction = shift[2];
            int diff = direction == 1 ? 1 : -1;
            timeline[start] += diff;
            timeline[end + 1] -= diff;
        }

        for (int i = 0; i < s.Length; ++i)
        {
            currShift = (currShift + timeline[i]) % 26;
            int num = (s[i] - 'a' + currShift + 26) % 26;
            sb.Append((char)('a' + num));
        }

        return sb.ToString();
    }
}

Was this solution helpful?