Problem

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.

Examples

Example 1:

1
2
3
4
5

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:

1
2
3
4
5
6
7

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

Solution

Method 1 - Net Shift (Aggregate Shift)

Intuition

Instead of performing each shift operation one by one, we can combine all shifts into a single net shift. Left and right shifts can be combined by adding/subtracting their amounts, and the result can be applied in one go.

Approach

Sum all left shifts and right shifts. The net shift is (right - left) modulo the string length. Apply the net shift to the string in one operation.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

#include <vector>
#include <string>
using namespace std;
class Solution {
public:
    string stringShift(string s, vector<vector<int>>& shift) {
        int n = s.size(), net = 0;
        for (auto& op : shift) net += (op[0] ? op[1] : -op[1]);
        net = ((net % n) + n) % n;
        return s.substr(n - net) + s.substr(0, n - net);
    }
};
1
2
3
4
5
6
7
8

func stringShift(s string, shift [][]int) string {
    n, net := len(s), 0
    for _, op := range shift {
        if op[0] == 0 { net -= op[1] } else { net += op[1] }
    }
    net = ((net % n) + n) % n
    return s[n-net:] + s[:n-net]
}
1
2
3
4
5
6
7
8

class Solution {
    public String stringShift(String s, int[][] shift) {
        int n = s.length(), net = 0;
        for (int[] op : shift) net += (op[0] == 1 ? op[1] : -op[1]);
        net = ((net % n) + n) % n;
        return s.substring(n - net) + s.substring(0, n - net);
    }
}
1
2
3
4
5
6
7
8
9

class Solution {
    fun stringShift(s: String, shift: Array<IntArray>): String {
        val n = s.length
        var net = 0
        for (op in shift) net += if (op[0] == 1) op[1] else -op[1]
        net = ((net % n) + n) % n
        return s.substring(n - net) + s.substring(0, n - net)
    }
}
1
2
3
4
5
6

def stringShift(s: str, shift: list[list[int]]) -> str:
    n, net = len(s), 0
    for d, a in shift:
        net += a if d == 1 else -a
    net = (net % n + n) % n
    return s[-net:] + s[:-net] if net else s
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

fn string_shift(s: &str, shift: Vec<Vec<i32>>) -> String {
    let n = s.len();
    let mut net = 0;
    for op in shift.iter() {
        if op[0] == 1 { net += op[1]; } else { net -= op[1]; }
    }
    let net = ((net % n as i32) + n as i32) % n as i32;
    let bytes = s.as_bytes();
    let mut res = Vec::with_capacity(n);
    res.extend_from_slice(&bytes[(n as i32 - net) as usize..]);
    res.extend_from_slice(&bytes[..(n as i32 - net) as usize]);
    String::from_utf8(res).unwrap()
}
1
2
3
4
5
6
7

function stringShift(s: string, shift: number[][]): string {
    const n = s.length;
    let net = 0;
    for (const [d, a] of shift) net += d === 1 ? a : -a;
    net = ((net % n) + n) % n;
    return s.slice(n - net) + s.slice(0, n - net);
}

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(n)