Domain 1EasyCORE

Perform String Shifts

We are given a string `s` consisting of lowercase English letters and a matrix `shift`, where each element in `shift` is an array `[direction, amount]`. The `direction` can be either `0` (left shift) or `1` (right shift), and the `amount` specifies how many positions to shift the string. Our task is to perform all the shifts sequentially and return the final string.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Array#Math

1427. Perform String Shifts

Model: qwen2.5-coder:14b
Topics: Array,Math
FAANG asked: 0
Acceptance rate: 53.5%


Problem Breakdown

We are given a string s consisting of lowercase English letters and a matrix shift, where each element in shift is an array [direction, amount]. The direction can be either 0 (left shift) or 1 (right shift), and the amount specifies how many positions to shift the string. Our task is to perform all the shifts sequentially and return the final string.

Inputs:

  • A string s containing lowercase English letters.
  • A matrix shift, where each element is an array [direction, amount].

Outputs:

  • The final string after performing all the specified shifts.

Implicit Constraints or Tricky Edge Cases:

  • If the total shift amount is zero, the string remains unchanged.
  • If the total shift amount is equal to the length of the string, the string also remains unchanged.
  • Handling large amount values efficiently by using modulo operation with the string length.

Intuition

A brute-force approach would involve performing each shift individually and updating the string accordingly. However, this approach can be inefficient in terms of time complexity, especially if there are many shifts or large amounts to shift.

The key insight is to first compute the net effect of all shifts combined. This can be done by maintaining a balance between left and right shifts. After calculating the net shift, we perform a single shift operation based on this net value. This reduces the number of operations significantly and optimizes the solution.

Approach

  1. Initialize a Balance Counter:

    • Create a variable balance to keep track of the net effect of all shifts.
  2. Compute Net Shift:

    • Iterate through each shift operation in the shift matrix:
      • If the direction is 0 (left shift), subtract the amount from balance.
      • If the direction is 1 (right shift), add the amount to balance.
    • After processing all shifts, balance will represent the net number of positions to shift the string.
  3. Normalize the Balance:

    • Since shifting by the length of the string results in the same string, we can use modulo operation to normalize the balance:
      • balance = balance % len(s)
    • If balance is negative, convert it to a positive equivalent by adding the length of the string:
      • if balance < 0: balance += len(s)
  4. Perform Final Shift:

    • If balance is zero, return the original string as no shift is needed.
    • Otherwise, perform a single left or right shift based on the value of balance.
  5. Return the Resulting String:

Complexity Analysis

  • Time Complexity: O(n + m), where n is the length of the string s and m is the number of shifts. We iterate through the shifts to compute the balance (O(m)) and then perform a single shift operation (O(n)).
  • Space Complexity: O(1) for the additional variables used, excluding the input and output.

Solution

def stringShift(s: str, shift: List[List[int]]) -> str:
    # Step 1: Compute net balance of shifts
    balance = 0
    for direction, amount in shift:
        if direction == 0:
            balance -= amount
        else:
            balance += amount
    
    # Step 2: Normalize the balance using modulo operation
    balance %= len(s)
    
    # Step 3: Handle negative balance by converting it to positive equivalent
    if balance < 0:
        balance += len(s)
    
    # Step 4: Perform final shift based on the balance
    if balance == 0:
        return s
    
    # Perform left or right shift based on balance
    return s[-balance:] + s[:-balance]

Edge Cases Handled

  • Empty Shifts: If shift is empty, the function returns the original string.
  • Zero Net Shift: If the net shift amount is zero after processing all shifts, the function returns the original string.
  • Large Amount Values: The use of modulo operation ensures that large shift amounts are handled efficiently without unnecessary rotations.
  • Single Character String: For a single-character string, any number of shifts results in the same character.