Code Implementation

class Solution:
    def stringShift(self, s: str, shift: List[List[int]]) -> str:
        total = 0
        for direction, amount in shift:
            if direction == 0:
                total -= amount
            else:
                total += amount
        total = total % len(s)
        return s[-total:] + s[:-total] if total else s
      

class Solution {
public:
    string stringShift(string s, vector<vector<int>>& shift) {
        int total = 0;
        int n = s.size();
        for (auto &op : shift) {
            if (op[0] == 0)
                total -= op[1];
            else
                total += op[1];
        }
        total = ((total % n) + n) % n;
        return s.substr(n - total) + s.substr(0, n - total);
    }
};
      

class Solution {
    public String stringShift(String s, int[][] shift) {
        int total = 0;
        int n = s.length();
        for (int[] op : shift) {
            if (op[0] == 0)
                total -= op[1];
            else
                total += op[1];
        }
        total = ((total % n) + n) % n;
        return s.substring(n - total) + s.substring(0, n - total);
    }
}
      

var stringShift = function(s, shift) {
    let total = 0;
    let n = s.length;
    for (let [direction, amount] of shift) {
        if (direction === 0) {
            total -= amount;
        } else {
            total += amount;
        }
    }
    total = ((total % n) + n) % n;
    return s.slice(n - total) + s.slice(0, n - total);
};
      

Problem Description

You are given a string s and a list of shift operations shift, where each operation is represented as a pair [direction, amount]. The direction can be:

• 0 for a left shift (move characters from the start to the end)
• 1 for a right shift (move characters from the end to the start)

Constraints:

• 1 ≤ s.length ≤ 100
• shift.length is between 1 and 100
• Each amount is between 0 and 100
• There is always one valid final result

Thought Process

At first glance, the problem suggests simulating each shift operation one by one. For every operation, we could slice the string and concatenate the parts according to the direction and amount. However, performing this for every operation could be inefficient, especially if there are many shifts.

On closer inspection, we realize that consecutive shifts can be combined: a left shift followed by a right shift is equivalent to a single net shift. Thus, instead of applying each shift in sequence, we can calculate the total net shift and apply it just once.

This optimization is crucial for both performance and code simplicity. It's like tracking how far you've moved left or right in total, rather than retracing every individual step.

Solution Approach

• Step 1: Initialize a variable to keep track of the net shift amount. Left shifts decrease this value, right shifts increase it.
• Step 2: Loop through all shift operations and update the net shift accordingly.
• Step 3: Since shifting the string by its length results in the same string, take the net shift modulo the string's length to keep it within bounds.
• Step 4: Convert any negative net shifts (which correspond to left shifts) into equivalent positive right shifts using modulo arithmetic.
• Step 5: Perform the final shift in one operation by slicing and concatenating the string appropriately:
  • For a right shift of k, move the last k characters to the front.
  • For a left shift, this is equivalent to a right shift of len(s) - k.

This approach reduces the problem to a single string operation, regardless of the number of shift commands.

Example Walkthrough

Let's use the example: s = "abcdefg", shift = [[1,1],[1,1],[0,2],[1,3]].

1. First shift: right by 1 → "gabcdef"
2. Second shift: right by 1 → "fgabcde"
3. Third shift: left by 2 → "abcde fg"
4. Fourth shift: right by 3 → "efgabcd"

But instead of applying each, we calculate the net shift:

• Right: 1 + 1 + 3 = 5
• Left: 2
• Net shift: 5 - 2 = 3 (right shift by 3)

Time and Space Complexity

• Brute-force approach: If we performed every shift operation individually, each could take O(N) time (where N is the string length), and with M operations, total time is O(M*N).
• Optimized approach: We sum all shifts in O(M), and perform a single shift in O(N), so total time is O(M + N).
• Space complexity: Both approaches use O(N) space for the result string.

The optimized approach is much faster, especially when the number of operations is large.

Summary

By recognizing that multiple shift operations can be combined into a single net shift, we dramatically simplify the problem. This insight leads to a concise and efficient solution: just sum the left and right shifts, normalize the result, and perform one final string operation. The elegance comes from reducing repeated work and leveraging properties of modular arithmetic.