Perform String Shifts

#57 Most AskedEasy

Perform String Shifts #57 Most Asked

Easy

7 views

Topics:

Strings

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 shifts are applied.

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 lowercase English letters.
1 <= shift.length <= 100
shift[i].length == 2
0 <= shift[i][0] <= 1
0 <= shift[i][1] <= 100

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the constraints on the length of the string `s` and the number of shift operations in the `shift` list?
Can the `amount` in a shift operation be zero or negative?
If the total shift amount (left shifts minus right shifts) exceeds the length of the string, should I take the result modulo the string length?
Is the `shift` list guaranteed to be valid, or do I need to handle cases where it's null or empty?
What type are the `direction` and `amount` values, and are there any specific data type constraints for them beyond being integers?

Brute Force Solution

Approach

The brute force approach to string shifts means we're going to try every possible shift operation one at a time. For each shift operation, we actually perform the shift and then move on to the next shift operation to be performed on the original string. We then modify the string accordingly.

Here's how the algorithm would work step-by-step:

Look at the first shift instruction.
Create a modified copy of the original string.
Perform the shift operation, either moving characters to the left or to the right, based on the instructions on the modified string copy.
Now, consider the second shift instruction, applying it to the original string, creating another modified copy.
Perform that shift operation on its respective modified string copy.
Continue this process for every single shift instruction provided, each time working from the original string.
For each operation, make sure you are making a unique copy of the original string as the basis for each shift calculation.

Code Implementation

def perform_string_shifts_brute_force(input_string, shifts):
    modified_string = input_string

    for shift in shifts:
        direction = shift[0]
        amount = shift[1]

        # Handle left shift operation
        if direction == 0:

            amount_to_shift = amount % len(modified_string)
            shifted_characters = modified_string[:amount_to_shift]

            # Move characters from beginning to end
            modified_string = modified_string[amount_to_shift:] + shifted_characters

        # Handle right shift operation
        else:
            amount_to_shift = amount % len(modified_string)
            shifted_characters = modified_string[-amount_to_shift:]

            # Move characters from end to beginning
            modified_string = shifted_characters + modified_string[:-amount_to_shift]

    return modified_string

Big(O) Analysis

Time Complexity

O(n*m) – The algorithm iterates through m shift operations. For each shift operation, it creates a copy of the original string of length n and then performs the shift. Shifting itself takes O(n) time as characters need to be moved. Since there are m such shift operations done sequentially, the total time complexity becomes O(n*m), where n is the length of the string and m is the number of shift operations.

Space Complexity

O(N) – For each shift operation, the brute force approach creates a modified copy of the original string. Since there can be multiple shift operations, and each operation acts on the original string, each shift requires duplicating the original string of length N, resulting in an auxiliary string of length N for each shift operation. Although each string copy is temporary, the need to create these copies impacts the memory footprint. Therefore, the algorithm has a space complexity of O(N), where N is the length of the original string.

Optimal Solution

Approach

The problem asks to shift characters in a string either to the left or right based on a series of instructions. Instead of performing shifts one by one, we can find the net shift first. Then, we efficiently perform a single shift operation on the whole string based on the net shift.

Here's how the algorithm would work step-by-step:

First, analyze all the shift instructions. For each instruction, determine if it's a left shift or a right shift and by how many positions.
Calculate the total shift amount. Treat left shifts as negative shifts and right shifts as positive shifts. Sum them all up.
Simplify the total shift amount. If it's larger than the length of the string, take the remainder after dividing by the string length. This gives the equivalent shift within one string cycle.
Adjust the sign of the simplified shift amount so that a positive value always means a right shift. This will make it easier to perform the final shift operation.
Perform the final shift. Split the string into two parts based on the adjusted shift amount and swap the positions of these parts. Specifically, if the adjusted shift amount is X, take the last X characters of the original string and put them at the beginning. Then, take the remaining characters from the original string and put them after the characters you just moved.
Return the shifted string.

Code Implementation

def perform_string_shifts(input_string, shifts):
    total_shift = 0
    for shift in shifts:
        direction = shift[0]
        amount = shift[1]
        if direction == 0:
            total_shift -= amount
        else:
            total_shift += amount

    string_length = len(input_string)

    # Modulo handles shifts larger than string length.
    net_shift = total_shift % string_length

    # String slicing achieves the shift operation.
    if net_shift < 0:
        net_shift = abs(net_shift)
        shifted_string = input_string[net_shift:] + input_string[:net_shift]
    else:
        shifted_string = input_string[-net_shift:] + input_string[:-net_shift]

    return shifted_string

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the shift instructions once to calculate the net shift, which takes O(m) time where m is the number of shift instructions. The string shift operation involves creating substrings and concatenating them, which takes O(n) time where n is the length of the string. Since m is independent of n and the substring operation is the dominant factor, the overall time complexity is O(n). The calculation of the net shift and simplification are O(m) but assumed to be independent and smaller than the length of the string n.

Space Complexity

O(1) – The algorithm calculates the net shift and simplifies it, storing these values in a few integer variables. It then performs a string split and concatenation, but these operations can be done in-place using Python's string slicing which creates new string objects, but it is assigned immediately to the original variable and doesn't create significant extra space. The amount of extra memory used for these integers is constant and does not depend on the length of the string (N), so the space complexity is O(1).

Edge Cases

Case	How to Handle
Empty string s	Return an empty string if the input string `s` is empty as there's nothing to shift.
Null string s or null shift array	Throw an IllegalArgumentException or return null to indicate invalid input; better yet validate the inputs prior to shift operations.
Empty shift array	Return the original string `s` as there are no shift operations to perform.
Large amount in shift operations exceeding string length	Take the amount modulo the length of the string to avoid unnecessary computations and stay within bounds.
String with only one character	The shifted string is the same as the input string since shifting a single character string does nothing effectively.
String with all identical characters	Shifting doesn't change the output visibly, but the algorithm should still execute correctly.
Large input string and a large number of shifts could cause performance issues	Optimize by using an efficient string manipulation method (e.g., using character array and modulo operations directly to minimize copying), and aggregate shifts before applying.
Amount is zero	Amount is 0 then it means no shift should happen for that shift operation.

Empty string s

How to Handle:

Return an empty string if the input string `s` is empty as there's nothing to shift.

Null string s or null shift array

How to Handle:

Throw an IllegalArgumentException or return null to indicate invalid input; better yet validate the inputs prior to shift operations.

Empty shift array

How to Handle:

Return the original string `s` as there are no shift operations to perform.

Large amount in shift operations exceeding string length

How to Handle:

Take the amount modulo the length of the string to avoid unnecessary computations and stay within bounds.

String with only one character

How to Handle:

The shifted string is the same as the input string since shifting a single character string does nothing effectively.

String with all identical characters

How to Handle:

Shifting doesn't change the output visibly, but the algorithm should still execute correctly.

Large input string and a large number of shifts could cause performance issues

How to Handle:

Optimize by using an efficient string manipulation method (e.g., using character array and modulo operations directly to minimize copying), and aggregate shifts before applying.

Amount is zero

How to Handle:

Amount is 0 then it means no shift should happen for that shift operation.