1427. Perform String Shifts

Problem Description

Given a string s and a list of shift operations, perform the shifts on the string and return the final result. Each shift operation is represented by an array [direction, amount], where direction is 0 for left shift and 1 for right shift, and amount is the number of positions to shift.

Example:

Input: s = "abc", shift = [[0, 1], [1, 2]]
Output: "cab"
Explanation:
- First operation shift left one bit => "bca"
- The second operation shifts right two places => "cab"

Solution Code

public class Solution {
    /**
     * @param s: the string
     * @param shift: the shift operations
     * @return: the string after shifts
     */
    public String stringShift(String s, int[][] shift) {
        int totalShift = 0;
        int n = s.length();
        
        // Calculate the net shift
        for (int[] sh : shift) {
            int direction = sh[0];
            int amount = sh[1];
            if (direction == 0) {
                totalShift -= amount;
            } else {
                totalShift += amount;
            }
        }
        
        // Normalize the total shift to be within the length of the string
        totalShift %= n;
        if (totalShift < 0) {
            totalShift += n;
        }
        
        // Perform the shift
        String result = s.substring(n - totalShift) + s.substring(0, n - totalShift);
        return result;
    }
}

Approach Name

Net Shift Calculation and Normalization

Intuition

The key insight is that multiple shifts can be combined into a single net shift. Left shifts and right shifts cancel each other out, so we can calculate the total shift by summing up the effects of all individual shifts. Once we have the net shift, we can perform a single shift operation to get the final result.

Algorithm

  1. Calculate Net Shift:

    • Iterate through the shift operations and calculate the total shift. Left shifts subtract from the total, and right shifts add to the total.
  2. Normalize the Shift:

    • Since shifting by the length of the string results in the same string, we can normalize the total shift by taking modulo with the length of the string. If the result is negative, adjust it to be positive.
  3. Perform the Shift:

    • Use the normalized shift to split the string and rearrange it to get the final result.

Complexity Analysis

  • Time Complexity: O(n + m), where n is the length of the string and m is the number of shift operations. We iterate through the shift operations once and perform a constant-time shift operation on the string.
  • Space Complexity: O(n), where n is the length of the string. We create a new string to store the result.
  1. Easy - ๐Ÿ”’ 1427. Perform String Shifts
  1. Easy - 3645. Perform String Shifts