💬 Discord
Sign In
NeetCode #17LC-1427EasyArrays & HashingNC Algo100
← Back to All Problems

#17 · #1427 · Perform String Shifts(字符串的左右移)

📌 Problem Statement & Constraints

You are given a string s and a 2D array shift where shift[i] = [direction, amount]. Direction 0 means shift left by amount, direction 1 means shift right by amount. Apply all shifts and return the final string. Constraints: 1 <= s.length <= 100, 1 <= shift.length <= 100, 0 <= amount <= s.length.

💡 Core Algorithmic Approaches

  1. Applying shifts one by one costs O(|s|) per shift. Instead, note that shifts commute and compose additively.
  2. Convert every shift to a signed offset: direction 0 contributes -amount, direction 1 contributes +amount.
  3. Sum the offsets and reduce modulo len(s). A positive total means a net right shift.
  4. Then perform one rotation: a right shift by k is s[-k:] + s[:-k].

💻 Benchmark Python3 Implementation

class Solution:
    def stringShift(self, s: str, shift: List[List[int]]) -> str:
        total = 0
        for direction, amount in shift:
            total += -amount if direction == 0 else amount   # left is negative
        n = len(s)
        total %= n                        # shifts are periodic
        if total == 0:
            return s
        return s[n - total:] + s[:n - total]                 # one rotation

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(|s| + q): O(q) to accumulate the offsets and O(|s|) for the single rotation. Naively applying each shift would be O(q * |s|).
💾 Space Complexity
O(|s|) for the new string.

⚠️ Interview Pitfalls & Follow-ups

  • Applying each shift separately: O(q * |s|) and much more code than summing first.
  • Forgetting % n: a total beyond n indexes out of range (or, in Python, silently produces the wrong rotation).
  • Sign confusion: direction 0 is left, so it contributes a negative offset when expressed as a right shift.
  • Handling total == 0 with the general formula: s[n:] + s[:n] is actually correct (s[n:] is empty), but the explicit branch is clearer and avoids a needless copy.