Perform String Shifts - CPP Solution

1. Introduction

This blog post addresses an interesting problem of string manipulation in C++: performing multiple shifts on a string based on given instructions. This problem is an excellent exercise in understanding string operations and handling edge cases in string manipulation.

Problem

Given a string s and a shift array where each element shift[i] = [direction, amount] represents a shift operation, perform the shifts on s. If direction is 0, shift to the left; if 1, shift to the right. The amount indicates the number of positions each shift is for. The task is to apply all these shifts to the string and return the final result.

2. Solution Steps

1. Compute the net shift amount by iterating over the shift array.

2. Normalize the net shift to fit within the length of the string.

3. Perform a left or right shift based on the net shift.

4. Implement left and right shift functions:

- A left shift moves characters from the start to the end.

- A right shift moves characters from the end to the start.

5. Return the shifted string.

3. Code Program

#include <iostream>
#include <vector>
using namespace std;

// Function to perform left shift
string leftShift(const string &s, int amount) {
    int n = s.length();
    amount %= n;
    return s.substr(amount) + s.substr(0, amount);
}

// Function to perform right shift
string rightShift(const string &s, int amount) {
    int n = s.length();
    amount %= n;
    return s.substr(n - amount) + s.substr(0, n - amount);
}

// Function to perform string shifts
string stringShift(string s, vector<vector<int>>& shift) {
    int netShift = 0;

    // Calculate the net shift amount
    for (auto &sh : shift) {
        if (sh[0] == 0) { // Left shift
            netShift -= sh[1];
        } else { // Right shift
            netShift += sh[1];
        }
    }

    // Normalize the net shift
    netShift %= (int)s.length();
    if (netShift > 0) {
        return rightShift(s, netShift);
    } else {
        return leftShift(s, -netShift);
    }
}

int main() {
    string s = "abcdefg";
    vector<vector<int>> shift = {{1, 1}, {1, 1}, {0, 2}, {1, 3}};
    cout << "Shifted string: " << stringShift(s, shift) << endl;
    return 0;
}

Output:

Shifted string: efgabcd

Explanation:

1. The input string "abcdefg" is processed with the shift operations {{1, 1}, {1, 1}, {0, 2}, {1, 3}}.

2. The net shift amount is calculated from the shift operations.

3. The net shift is normalized to the length of the string.

4. Depending on the net shift direction, a left or right shift is performed.

5. The shifted string "efgabcd" is the result of applying these operations, demonstrating an efficient way to manipulate strings based on shifting rules.