1427. Perform String Shifts 🔒

Description

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.

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 <= 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

Solutions

Solution 1: Simulation

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)\).

1
2
3
4
5

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]

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

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);
    }
}

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

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);
    }
};

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

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]
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

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);
}

Comments