Perform String Shifts

12
0

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 = 0 indicates a left rotation of the string.

  • direction = 1 indicates a right rotation of the string.

  • amount represents 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

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 Starts
int 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 is 1 (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

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 Starts
int 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.

StringTCS NQT

Read Similar Blogs

Comments0