1. Simulation

Intuition

A left shift moves characters from the front to the back, while a right shift moves characters from the back to the front. We can simulate each shift operation directly by slicing the string. Taking modulo of the shift amount by the string length handles cases where the shift exceeds the string size, since shifting by the full length returns the original string.

Algorithm

1. Iterate through each shift operation (direction, amount).
2. Take amount modulo the string length to handle large shifts.
3. If direction is 0 (left shift), move the first amount characters to the end: s = s[amount:] + s[:amount].
4. If direction is 1 (right shift), move the last amount characters to the front: s = s[-amount:] + s[:-amount].
5. Return the final string after all shifts.

class Solution:
    def stringShift(self, s: str, shift: List[List[int]]) -> str:
        for direction, amount in shift:
            amount %= len(s)
            if direction == 0:
                # Move necessary amount of characters from start to end
                s = s[amount:] + s[:amount]
            else:
                # Move necessary amount of characters from end to start
                s = s[-amount:] + s[:-amount]
        return s

Time & Space 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

---

2. Compute Net Shift

Intuition

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.

Algorithm

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.

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

Time & Space 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