Skip to main content
Talentd

Perform String Shifts - Solution & Explanation

EasyPremiumFree on FleetCodeArrayMathString6 min readAsked at: Goldman Sachs
Practice this problem

Problem Statement

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

  • directioni can be 0 (for left shift) or 1 (for right shift).
  • amounti 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
  • directioni is either 0 or 1.
  • 0 <= amounti <= 100

Approach Overview

Problem Overview: You receive a string and a list of shift operations. Each operation moves characters either left or right by a given amount. The goal is to apply all shifts and return the final string.

The key detail is that multiple shifts accumulate. Instead of physically shifting the string every time, you can combine the shifts mathematically and perform a single rotation.

Approach 1: Direct Simulation (O(n * m) time, O(n) space)

The most straightforward method processes each operation one by one and updates the string immediately. For a left shift, move the first k characters to the end. For a right shift, move the last k characters to the front. This can be implemented using substring slicing or manual concatenation.

Each shift requires rebuilding the string, which costs O(n) time. If there are m operations, the total complexity becomes O(n * m). Space complexity stays O(n) due to intermediate string copies. This method is easy to implement and works fine when the number of operations is small, but it becomes inefficient when many shifts are applied.

Approach 2: Net Shift Calculation (Simulation Optimization) (O(n + m) time, O(n) space)

A better strategy combines all shifts into a single net rotation. Iterate through the operations and track the total shift amount: treat left shifts as negative movement and right shifts as positive. After processing all operations, reduce the result using modulo n where n is the string length.

This converts multiple rotations into one final shift. If the final shift is positive, perform a right rotation; if negative, perform a left rotation. The rotation itself is done using substring slicing or concatenation: split the string and reorder the pieces.

The algorithm scans the operations once (O(m)) and performs one final rotation (O(n)). Total time complexity becomes O(n + m) with O(n) space for the resulting string. This approach relies on simple arithmetic from math and efficient manipulation of string segments.

Recommended for interviews: Interviewers expect the net shift approach. Direct simulation shows you understand the mechanics of rotation, but combining operations demonstrates stronger reasoning about cumulative effects. Recognizing that shifts can cancel each other out is the key insight. The implementation is simple once you compute the final offset and rotate the array-like structure of characters.

Solution

We can denote the length of the string s as n. Next, we traverse the array shift, accumulate to get the final offset x, then take x modulo n, the final result is to move the first n - x characters of s to the end.

The time complexity is O(n + m), where n and m are the lengths of the string s and the array shift respectively. The space complexity is O(1).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Direct SimulationO(n * m)O(n)When the number of operations is small or for quick prototyping
Net Shift Calculation (Optimized Simulation)O(n + m)O(n)General case with many shift operations; preferred interview solution

Video Solution

LeetCode Day 14 - String Shifts • Errichto Algorithms • 17,213 views views

Watch 9 more video solutions →

Frequently Asked Questions

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.

Ready to solve this problem?

Practice Perform String Shifts with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays