We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Perform String Shifts

Number: 1345

Difficulty: Easy

Paid? Yes

Companies: Goldman Sachs

Problem Description

Given a string and a list of shift operations where each operation specifies a direction (0 for left shift, 1 for right shift) and an amount, perform all the shifts and return the final string. A left shift removes characters from the start and appends them to the end, while a right shift removes characters from the end and prepends them to the beginning.

Key Insights

  • Consolidate all shifts by calculating a net shift: subtract for left shifts and add for right shifts.
  • Use modulo arithmetic with the string length to avoid unnecessary full rotations.
  • Slice the string based on the effective shift to construct the final string.

Space and Time Complexity

Time Complexity: O(n + m), where n is the length of the string and m is the number of shift operations.
Space Complexity: O(n) for the output string.

Solution

The solution involves computing the net shift value by iterating through the shift operations. Left shifts subtract from the net value, and right shifts add to the net value. After obtaining the cumulative shift, use modulo with the string length to normalize the shift, ensuring it lies within bounds. The final string is constructed by slicing the string into two parts and concatenating them appropriately. This approach leverages string slicing as the primary operation for shifting.

Code Solutions

# Python solution

def stringShift(s, shift):
    # Initialize the net shift counter
    net_shift = 0
    for direction, amount in shift:
        if direction == 0:
            net_shift -= amount  # Left shift reduces index
        else:
            net_shift += amount  # Right shift increases index
    
    # Normalize shift to be within bounds of the string length
    net_shift %= len(s)
    
    # A right shift can be simulated by taking the last net_shift characters
    # and concatenating them with the beginning of the string.
    return s[-net_shift:] + s[:-net_shift]

# Example usage
if __name__ == "__main__":
    s = "abcdefg"
    shift_operations = [[1,1],[1,1],[0,2],[1,3]]
    print(stringShift(s, shift_operations))  # Output: "efgabcd"
← Back to All Questions