Perform String Shifts

How it works

Instead of performing each shift individually, we can compute the net effect of all shifts. Left and right shifts cancel each other out, so we sum all left shifts as positive and all right shifts as negative (or vice versa). The final net shift tells us how much to rotate the string in one direction, avoiding redundant operations.

Steps

1. Initialize a counter for net left shifts.
2. For each shift, if direction is 0, add the amount to the counter. If direction is 1, subtract the amount.
3. Take the result modulo the string length, handling negative values to get a positive index.
4. Perform a single left rotation by the computed amount: s = s[leftShifts:] + s[:leftShifts].
5. Return the result.

Complexity

• Time complexity: O(N + L)
• Space complexity: O(L) extra space used

Where L is the length of the string and N is the length of the shift array

Things to watch for

Forgetting to Take Modulo of Shift Amount

When the shift amount exceeds the string length, shifting by len(s) positions returns the original string. Failing to take amount % len(s) before performing the shift can cause index out of bounds errors or inefficient operations when the shift amount is very large.

Confusing Left and Right Shift Directions

A left shift moves characters from the front to the back, while a right shift moves characters from the back to the front. Mixing up these directions or incorrectly implementing the slicing logic results in the wrong output. Always verify which direction corresponds to which direction value (0 for left, 1 for right).

from typing import List

class Solution:
    def stringShift(self, s: str, shift: List[List[int]]) -> str:
        # Count the number of left shifts. A right shift is a negative left shift.
        left_shifts = 0
        for direction, amount in shift:
            if direction == 1:
                amount = -amount
            left_shifts += amount

        # Convert back to a positive, do left shifts, and return.
        left_shifts %= len(s)
        s = s[left_shifts:] + s[:left_shifts]
        return s

class Solution {
public:
    string stringShift(string s, vector<vector<int>>& shift) {
        // Count the number of left shifts. A right shift is a negative left shift.
        int leftShifts = 0;

        for (auto& move : shift) {
            if (move[0] == 1) {
                move[1] = -move[1];
            }
            leftShifts += move[1];
        }

        // Convert back to a positive, do left shifts, and return.
        int n = s.length();
        leftShifts = ((leftShifts % n) + n) % n;
        s = s.substr(leftShifts) + s.substr(0, leftShifts);
        return s;
    }
};