String Shifts

Great problem to think about Pre-Processing before jumping into the actual core of the implementation, here it is: https://leetcode.com/problems/perform-string-shifts/

1427. Perform String Shifts

Easy

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

• direction can be 0 (for left shift) or 1 (for right shift). 
• amount 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
• 0 <= shift[i][0] <= 1
• 0 <= shift[i][1] <= 100

Accepted

36

Submissions

111,645

If you keep rotating the string for every single shift, you'll be spending a lot of crucial CPU cycles doing tasks that you really can avoid. The best approach though is to calculate the total number of rotations, and the direction, just by going thru the shifts array and perform simple calculations that will tell you the ultimate direction that you should use, as well as the final delta. Remember that you're only rotating back and forth, like a belt that you're pulling from left to right and vice-versa.
Once you do that, perform the rotation is O(Len(s)). Hence, the total execution time becomes O(Len(s) + Len(shifts))-time. Code is below, cheers, ACC.

    public class Solution
    {
        public string StringShift(string s, int[][] shift)
        {
            if (shift == null || shift.Length == 0) return null;

            int direction = shift[0][0];
            int delta = shift[0][1];

            for (int i = 1; i < shift.Length; i++)
            {
                if (shift[i][0] == direction)
                {
                    delta += shift[i][1];
                }
                else
                {
                    if (shift[i][1] > delta)
                    {
                        delta = shift[i][1] - delta;
                        direction = shift[i][0];
                    }
                    else
                    {
                        delta = delta - shift[i][1];
                    }
                }
            }

            return Rotate(s, direction, delta % s.Length);
        }

        private string Rotate(string s, int direction, int delta)
        {
            StringBuilder sb = new StringBuilder(s);

            if (direction == 0)
            {
                for (int i = s.Length - 1; i >= 0; i--)
                {
                    int index = i - delta;
                    if (index < 0) index += s.Length;

                    sb[index] = s[i];
                }
            }
            else
            {
                for (int i = 0; i < s.Length; i++)
                {
                    sb[(i + delta) % s.Length] = s[i];
                }
            }

            return sb.ToString();
        }
    }