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
scontaining 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
amountvalues 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
-
Initialize a Balance Counter:
- Create a variable
balanceto keep track of the net effect of all shifts.
- Create a variable
-
Compute Net Shift:
- Iterate through each shift operation in the
shiftmatrix:- If the direction is
0(left shift), subtract the amount frombalance. - If the direction is
1(right shift), add the amount tobalance.
- If the direction is
- After processing all shifts,
balancewill represent the net number of positions to shift the string.
- Iterate through each shift operation in the
-
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
balanceis negative, convert it to a positive equivalent by adding the length of the string:if balance < 0: balance += len(s)
- Since shifting by the length of the string results in the same string, we can use modulo operation to normalize the balance:
-
Perform Final Shift:
- If
balanceis zero, return the original string as no shift is needed. - Otherwise, perform a single left or right shift based on the value of
balance.
- If
-
Return the Resulting String:
Complexity Analysis
- Time Complexity: O(n + m), where n is the length of the string
sand 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
shiftis 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.