LeetCode 1427 - Perform String Shifts

This problem asks us to simulate a sequence of string shift operations on a given string s. Each operation in the shift

leetcodeeasyarraymathstring

LeetCode Problem 1427

Difficulty: 🟢 Easy
Topics: Array, Math, String

Solution

Problem Understanding

This problem asks us to simulate a sequence of string shift operations on a given string s.

Each operation in the shift matrix contains two values:

  • direction

  • 0 means shift left

  • 1 means shift right

  • amount

  • the number of positions to shift

A left shift removes characters from the front and appends them to the back. For example:

"abcde" -> left shift by 2 -> "cdeab"

A right shift removes characters from the back and inserts them at the front:

"abcde" -> right shift by 2 -> "deabc"

The goal is to apply all operations in order and return the final transformed string.

The input constraints are small:

  • s.length <= 100
  • shift.length <= 100

This means even a direct simulation approach would work within limits. However, the problem has a mathematical observation that allows a cleaner and more efficient solution.

The important insight is that multiple shifts can cancel each other out. For example:

  • left by 3
  • right by 3

results in no change at all.

Another important detail is that shifting by the length of the string produces the original string again. For example:

"abcdef" shifted right by 6 -> "abcdef"

So only the shift amount modulo len(s) matters.

Several edge cases are important:

  • A shift amount may be 0, meaning no change.
  • The total effective shift may become negative if left shifts dominate.
  • The total shift may exceed the string length many times.
  • The string may have length 1, where every shift leaves the string unchanged.

The problem guarantees that the input format is valid, so we do not need to handle malformed operations.

Approaches

Brute Force Approach

The brute force solution directly simulates every operation exactly as described.

For each operation:

  • If it is a left shift, repeatedly move characters from the front to the back.
  • If it is a right shift, repeatedly move characters from the back to the front.

This produces the correct result because it follows the problem statement literally.

However, repeated character movement is inefficient. If the string has length n and there are m operations, each operation may cost up to O(n) time. In the worst case, the total complexity becomes O(m * n).

Although the constraints are small enough for this to pass, it performs unnecessary repeated work.

Optimal Approach

The key observation is that all shifts can be combined into one net shift.

A right shift increases the effective shift amount, while a left shift decreases it.

For example:

left 2
right 5
left 1

becomes:

-2 + 5 - 1 = +2

which means the final result is simply a right shift by 2.

After computing the total shift:

  • Reduce it modulo the string length.
  • Perform exactly one final rotation.

This avoids repeated intermediate transformations and makes the implementation much cleaner.

Approach Time Complexity Space Complexity Notes
Brute Force O(m × n) O(n) Simulates every shift operation directly
Optimal O(m + n) O(n) Combines all shifts into one net rotation

Where:

  • m is the number of shift operations
  • n is the length of the string

Algorithm Walkthrough

  1. Initialize a variable called net_shift to 0.

This variable stores the combined effect of all operations. 2. Iterate through every operation in shift.

Each operation contains:

  • direction
  • amount
  1. Update the net shift based on the direction.
  • If direction == 1, add amount because right shifts move characters toward the front.
  • If direction == 0, subtract amount because left shifts move characters toward the back.
  1. Reduce the total shift using modulo.

Since rotating a string by its own length returns the original string, compute:

net_shift %= len(s)

This keeps the shift within valid bounds.

  1. Construct the final rotated string.

A right shift by k means:

  • take the last k characters
  • place them in front
  • append the remaining prefix

This becomes:

s[-k:] + s[:-k]
  1. Return the resulting string.

Why it works

Every left shift and right shift is a cyclic rotation. Cyclic rotations are additive, meaning multiple rotations can be combined into a single equivalent rotation.

Because:

  • right shifts contribute positively
  • left shifts contribute negatively

the sum of all operations represents the final net rotation.

Modulo arithmetic guarantees that rotations larger than the string length are reduced to their equivalent minimal rotation. Therefore, performing one final rotation produces exactly the same result as executing every operation individually.

Python Solution

from typing import List

class Solution:
    def stringShift(self, s: str, shift: List[List[int]]) -> str:
        net_shift = 0
        n = len(s)

        for direction, amount in shift:
            if direction == 1:
                net_shift += amount
            else:
                net_shift -= amount

        net_shift %= n

        return s[-net_shift:] + s[:-net_shift]

The implementation begins by initializing net_shift, which accumulates the total effect of all operations.

The loop processes every shift instruction. Right shifts increase the value, while left shifts decrease it. This converts many operations into one mathematical result.

After processing all operations, the modulo operation ensures the shift amount stays within the string length.

Finally, the string slicing expression performs the rotation efficiently:

  • s[-net_shift:] extracts the suffix that moves to the front
  • s[:-net_shift] extracts the remaining prefix

Concatenating them produces the correctly rotated string.

One subtle detail is that Python slicing handles 0 cleanly:

s[-0:] == s
s[:-0] == ""

So the implementation works even when the effective shift is zero.

Go Solution

func stringShift(s string, shift [][]int) string {
    netShift := 0
    n := len(s)

    for _, operation := range shift {
        direction := operation[0]
        amount := operation[1]

        if direction == 1 {
            netShift += amount
        } else {
            netShift -= amount
        }
    }

    netShift %= n

    if netShift < 0 {
        netShift += n
    }

    return s[n-netShift:] + s[:n-netShift]
}

The Go implementation follows the same logic as the Python version.

One important difference is modulo behavior. In Python, negative modulo results are automatically converted into positive values. In Go, negative values remain negative, so we explicitly adjust:

if netShift < 0 {
    netShift += n
}

Go strings are immutable, just like Python strings, so constructing the final answer requires concatenating slices into a new string.

Worked Examples

Example 1

Input:
s = "abc"
shift = [[0,1],[1,2]]

Initial state:

Step Operation Net Shift
Start None 0
1 Left shift by 1 -1
2 Right shift by 2 1

Now compute:

1 % 3 = 1

Final rotation is right by 1.

Split the string:

Part Value
Last 1 character "c"
Remaining prefix "ab"

Result:

"c" + "ab" = "cab"

Final answer:

"cab"

Example 2

Input:
s = "abcdefg"
shift = [[1,1],[1,1],[0,2],[1,3]]

Track the net shift:

Step Operation Net Shift
Start None 0
1 Right shift by 1 1
2 Right shift by 1 2
3 Left shift by 2 0
4 Right shift by 3 3

Now compute:

3 % 7 = 3

Final rotation is right by 3.

Split the string:

Part Value
Last 3 characters "efg"
Remaining prefix "abcd"

Result:

"efg" + "abcd" = "efgabcd"

Final answer:

"efgabcd"

Complexity Analysis

Measure Complexity Explanation
Time O(m + n) We process all operations once, then build the final rotated string once
Space O(n) The resulting rotated string requires new string storage

The algorithm performs a single pass through the shift array and a single final string construction. Since string slicing and concatenation create a new string of size n, the overall space complexity is linear in the string length.

Test Cases

from typing import List

class Solution:
    def stringShift(self, s: str, shift: List[List[int]]) -> str:
        net_shift = 0
        n = len(s)

        for direction, amount in shift:
            if direction == 1:
                net_shift += amount
            else:
                net_shift -= amount

        net_shift %= n

        return s[-net_shift:] + s[:-net_shift]

sol = Solution()

assert sol.stringShift("abc", [[0, 1], [1, 2]]) == "cab"  # Example 1
assert sol.stringShift("abcdefg", [[1, 1], [1, 1], [0, 2], [1, 3]]) == "efgabcd"  # Example 2

assert sol.stringShift("a", [[0, 100]]) == "a"  # Single character string
assert sol.stringShift("abcde", [[1, 5]]) == "abcde"  # Shift equal to string length
assert sol.stringShift("abcde", [[1, 10]]) == "abcde"  # Shift multiple of length

assert sol.stringShift("abcde", [[0, 1]]) == "bcdea"  # Simple left shift
assert sol.stringShift("abcde", [[1, 1]]) == "eabcd"  # Simple right shift

assert sol.stringShift("abcdef", [[0, 2], [1, 2]]) == "abcdef"  # Shifts cancel out

assert sol.stringShift("abcdef", [[0, 8]]) == "cdefab"  # Large left shift
assert sol.stringShift("abcdef", [[1, 8]]) == "efabcd"  # Large right shift

assert sol.stringShift("xyz", [[0, 0], [1, 0]]) == "xyz"  # Zero shifts only
Test Why
"abc" with mixed shifts Validates the basic example
"abcdefg" with multiple operations Validates combining many shifts
Single character string Ensures trivial strings work correctly
Shift equal to length Confirms modulo behavior
Shift larger than length Tests repeated rotations
Simple left shift Verifies left rotation logic
Simple right shift Verifies right rotation logic
Canceling operations Ensures net shift computation works
Large left shift Tests modulo reduction
Large right shift Tests modulo reduction
Zero shifts Ensures no-op operations behave correctly

Edge Cases

One important edge case occurs when the total shift is larger than the string length. For example, shifting a string of length 5 by 12 positions is equivalent to shifting by 2. A naive implementation that repeatedly rotates characters may waste time doing unnecessary work. This implementation handles the issue correctly by reducing the final shift with modulo arithmetic.

Another important case is when left and right shifts cancel each other out. For example:

left 3
right 3

should leave the string unchanged. Bugs often appear when implementations process shifts independently instead of combining them mathematically. By accumulating a single net_shift, the algorithm naturally handles cancellation correctly.

A third edge case involves strings of length 1. Any shift operation on a single-character string must return the original string. Some implementations may accidentally produce invalid slice boundaries or redundant work. Because the modulo result becomes 0, the slicing expression safely returns the original string unchanged.

A final subtle case is when the effective shift becomes negative. For example:

left 4
right 1

produces a net shift of -3. The modulo operation converts this into the equivalent positive rotation. This guarantees the final slicing indices remain valid and consistent.