Given a string s consisting of lowercase English characters and a 2D array shift. Each element of the array contains two values: [direction, amount].
direction = 0indicates a left rotation of the string.direction = 1indicates a right rotation of the string.amountrepresents how many positions the string should be rotated.
In a left rotation, the first character moves to the end of the string. In a right rotation, the last character moves to the beginning. Apply all the given operations in the specified order and return the resulting string.
Example 1
Input: s = "xyz", shift = [[1, 2], [0, 1]]
Output: "zxy"
Explanation:
[1,2]: Rotate the string 2 positions to the right: "xyz" → "yzx".
[0,1]: Rotate the string 1 position to the left: "yzx" → "zxy".
Example 2
Input: s = "abcdef", shift = [[0, 2], [1, 3]]
Output: "efabcd"
Explanation:
[0,2]: Rotate the string 2 positions to the left: "abcdef" → "cdefab".
[1,3]: Rotate the string 3 positions to the right: "cdefab" → "efabcd".
Brute Force Approach
The most direct idea is to perform each shift operation one by one in the given order. For every operation, check the direction and rotate the string accordingly. A left shift moves the first few characters to the end, while a right shift moves the last few characters to the beginning. Using modulo (%) with the string length avoids unnecessary rotations because shifting a string by its full length brings the string back to its original form.
Algorithm
Iterate through all the given shift operations and extract the shifting direction with the number of positions.
Apply modulo with the string length to avoid unnecessary full rotations.
For a left shift, the first few characters are moved to the end of the string using
substr().For a right shift, the last few characters are moved to the beginning of the string using
substr().Repeat the process until all shift operations are completed.
Return the final modified string.
Dry Run
Perform String Shifts - Brute
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Function to perform string shift operations string stringShift(string s, vector<vector<int>>& shift) { // Iterate through all shift operations for (const auto& op : shift) { // Get the direction and shift amount int dir = op[0]; int amt = op[1]; // Normalize the shift amount amt %= s.size(); // Perform left shift if (dir == 0) { s = s.substr(amt) + s.substr(0, amt); } // Perform right shift else { s = s.substr(s.size() - amt) + s.substr(0, s.size() - amt); } } return s; }};// Driver Code Startsint main() { Solution sol; string s = "xyz"; vector<vector<int>> shift = {{1, 2}, {0, 1}}; cout << "Output: " << sol.stringShift(s, shift) << endl; return 0;}Complexity Analysis
Time Complexity:
O(M×A×N), where M represents the total number of shift operations, A is the average number of positions shifted, and N is the length of the string.Space Complexity:
O(1)auxiliary space, as no extra data structures are used. However, temporary strings may be created during substring operations.
Optimal Approach
The most efficient idea is to combine all the given shift operations into a single net shift instead of modifying the string after every operation. A left shift moves characters towards the beginning, so the shift amount is considered negative. A right shift moves characters towards the end, so the shift amount is considered positive.
By calculating the sum of all shift operations, the final direction and number of positions can be determined. Modulo with the string length eliminates unnecessary full rotations. Finally, a single string rotation is performed based on the net shift value, reducing the number of operations required.
Algorithm
Firstly a variable is initialized to store the net shift value.
Iterate through all the given shift operations.
If the direction is
0(left shift), subtract the shift amount from the net shift value and if it is1(right shift), add the shift amount to the net shift value.After processing all operations, apply modulo with the string length to normalize the final shift.
Check the net shift value:
If positive, perform a right rotation by moving the last few characters to the beginning.
If negative, convert the value to positive and perform a left rotation by moving the first few characters to the end.
If zero, return the original string without any modification.
Return the final string
Dry Run
Perform String Shifts - Optimal
Solution
#include <bits/stdc++.h>using namespace std;class Solution {public: // Function to perform string shift operations string stringShift(string s, vector<vector<int>>& shift) { long long netShift = 0; int n = s.size(); // Calculate the net shift value for (const auto& op : shift) { // Check for left shift if (op[0] == 0) { netShift -= op[1]; } // Check for right shift else { netShift += op[1]; } } // Normalize the shift within the string length netShift %= n; // Perform right shift if (netShift > 0) { return s.substr(n - netShift) + s.substr(0, n - netShift); } // Perform left shift else if (netShift < 0) { netShift = -netShift; return s.substr(netShift) + s.substr(0, netShift); } // Return the original string if no shift is required else { return s; } }};// Driver Code Startsint main() { Solution sol; string s = "xyz"; vector<vector<int>> shift = {{1, 2}, {0, 1}}; cout << "Output: " << sol.stringShift(s, shift) << endl; return 0;}Complexity Analysis
• Time Complexity: O(N + M), where N is the length of the string and M is the number of shift operations. Processing all shift operations takes O(M) time, while performing the final string rotation takes O(N) time due to substring creation and concatenation.
• Space Complexity: O(N), as temporary strings created during substring operations and concatenation may require O(N) auxiliary space. The net shift calculation itself requires only O(1) extra space.
Interview follow-up Questions
Modulo by zero is undefined. An empty string should be handled separately before performing any shift calculations.
Be the first to add a comment.