String Manipulation — Perform String Shifts

LeetCode: https://leetcode.com/explore/challenge/card/30-day-leetcoding-challenge/529/week-2/3299/

You are given a string s containing lowercase English letters, and a matrix shift, where shift[i] = [direction, amount]

0 means left shift, and 1 means right shift.

Input: s = "abc", shift = [[0, 1], [1, 2]]
Output: "cab"

Solution:

Shifting the string as we traverse through the shift array would be too expensive. Instead, we can just count the total left shift times and shift the string once.

1. For loop iterate through the shift array
2. Inside the for loop, add if it’s left shift, subtract if it’s right shift.
3. If the number of total left shifts needed is greater than the length of the string divide the number by the length of the string and take the remainder.
4. Return the left-shifted string

Complexity Analysis:

Let n be the length of the shift array and k be that of the string.
Time Complexity: O(n + k)
Going through the shift array would take O(n) and string slicing would also take O(k). Both of these depend on the input size.
Space Complexity: O(k)
When slicing a string in Python, it copies the data to a new string object. Therefore, it would also cost O(k).