Perform String Shifts solution and explanation
9 more videos on this problem
Perform string shifts | Leetcode | String rotationTechdose · 9:33 · 17K views
LeetCode 30 day Challenge | Day 14 | Perform String Shifts | LeetCode 1427Knowledge Center · 16:38 · 6K views
perform string shifts leetcode | perform string shifts python| leetcode | amazon interview questionthecodingworld · 5:30 · 3K views
Perform String Shifts (LeetCode Day 14 Question) | Programming TutorialsProgramming Tutorials · 15:39 · 3K views
Perform String Shifts [0ms] - LeetCode Day 14 Challengedaose · 15:47 · 445 views
Perform String Shifts | leetcode 30 days | hindiCodebix · 7:35 · 295 views
Perform String Shifts [LeetCode 1427] | Strings | Approach and IntuitionCodeTree · 12:45 · 280 views
Leetcode 1427 Perform String ShiftsRen Zhang · 9:18 · 242 views
LeetCode Day 14 - String ShiftsErrichto Algorithms · 7:01 · 17K views
Performing String Shifts Python (LeetCode)Satyanarayana Gokavarapu · 6:34 · 414 views
The problem
You are given a string s containing lowercase English letters, and a matrix shift, where shift[i] = [directioni, amounti]:
directionican be0(for left shift) or1(for right shift).amountiis the amount by which stringsis to be shifted.- A left shift by 1 means remove the first character of
sand append it to the end. - Similarly, a right shift by 1 means remove the last character of
sand 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 <= 100sonly contains lower case English letters.1 <= shift.length <= 100shift[i].length == 2directioniis either0or1.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).
class Solution:
def stringShift(self, s: str, shift: List[List[int]]) -> str:
x = sum((b if a else -b) for a, b in shift)
x %= len(s)
return s[-x:] + s[:-x]class Solution {
public String stringShift(String s, int[][] shift) {
int x = 0;
for (var e : shift) {
if (e[0] == 0) {
e[1] *= -1;
}
x += e[1];
}
int n = s.length();
x = (x % n + n) % n;
return s.substring(n - x) + s.substring(0, n - x);
}
}class Solution {
public:
string stringShift(string s, vector<vector<int>>& shift) {
int x = 0;
for (auto& e : shift) {
if (e[0] == 0) {
e[1] = -e[1];
}
x += e[1];
}
int n = s.size();
x = (x % n + n) % n;
return s.substr(n - x, x) + s.substr(0, n - x);
}
};function stringShift(s: string, shift: number[][]): string {
let x = 0;
for (const [a, b] of shift) {
x += a === 0 ? -b : b;
}
x %= s.length;
if (x < 0) {
x += s.length;
}
return s.slice(-x) + s.slice(0, -x);
}func stringShift(s string, shift [][]int) string {
x := 0
for _, e := range shift {
if e[0] == 0 {
e[1] = -e[1]
}
x += e[1]
}
n := len(s)
x = (x%n + n) % n
return s[n-x:] + s[:n-x]
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Direct Simulation | O(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 |
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.