Is Perform String Shifts easy or hard?

Perform String Shifts is categorized as an Easy problem. The core idea is recognizing that multiple shifts can be combined into one rotation using modular arithmetic.

Perform String Shifts Python/Java solution

In Python or Java, the solution computes the net shift first and then performs a single rotation using slicing or substring concatenation. Both implementations achieve O(n + m) time complexity and O(n) space.

How to solve Perform String Shifts in O(n)?

First accumulate all shift operations into a single net shift value. Convert left shifts to negative and right shifts to positive, then apply modulo with the string length. Perform one final rotation using substring slicing, which takes O(n) time.

What is the best approach for Perform String Shifts?

The best approach computes the net shift from all operations and performs a single rotation. Treat left shifts as negative and right shifts as positive, sum them, and reduce the result with modulo string length. This reduces repeated rotations and runs in O(n + m) time.

Is Perform String Shifts asked at Google/Amazon/Meta?

String manipulation and rotation problems like Perform String Shifts commonly appear in interviews at companies such as Amazon and Google. They test understanding of cumulative operations, modular arithmetic, and efficient string handling.

What data structure is used in Perform String Shifts?

The problem primarily uses strings treated as array-like character sequences. The algorithm relies on simple iteration and substring operations, along with modular arithmetic to compute the final rotation.

What is the time complexity of Perform String Shifts?

The optimal solution runs in O(n + m) time where n is the string length and m is the number of shift operations. You scan the operations once to compute the net shift and perform a single rotation of the string.

Description Hints 2 Solution Video 9:33

1427. Perform String Shifts

Easy56.0% acceptance1 companyPremium elsewhere, free here

You are given a string s containing lowercase English letters, and a matrix shift, where shift[i] = [direction_i, amount_i]:

direction_i can be 0 (for left shift) or 1 (for right shift).
amount_i is the amount by which string s is to be shifted.
A left shift by 1 means remove the first character of s and append it to the end.
Similarly, a right shift by 1 means remove the last character of s and add it to the beginning.

Return the final string after all operations.

Example 1:

Input: s = "abc", shift = [[0,1],[1,2]]
Output: "cab"
Explanation: 
[0,1] means shift to left by 1. "abc" -> "bca"
[1,2] means shift to right by 2. "bca" -> "cab"

Example 2:

Input: s = "abcdefg", shift = [[1,1],[1,1],[0,2],[1,3]]
Output: "efgabcd"
Explanation:  
[1,1] means shift to right by 1. "abcdefg" -> "gabcdef"
[1,1] means shift to right by 1. "gabcdef" -> "fgabcde"
[0,2] means shift to left by 2. "fgabcde" -> "abcdefg"
[1,3] means shift to right by 3. "abcdefg" -> "efgabcd"

Constraints:

1 <= s.length <= 100
s only contains lower case English letters.
1 <= shift.length <= 100
shift[i].length == 2
direction_iis either 0 or 1.
0 <= amount_i <= 100

Asked at 1 company

Goldman Sachs

Topics

Hints open one at a time

Hint 1

Intuitively performing all shift operations is acceptable due to the constraints.

Hint 2

You may notice that left shift cancels the right shift, so count the total left shift times (may be negative if the final result is right shift), and perform it once.

9:33

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
  def solve(self):
      pass


Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

"abc"
[[0,1],[1,2]]

Input

"abcdefg"
[[1,1],[1,1],[0,2],[1,3]]

Your code is saved on this device.Solution