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

Shifting Letters II

Number: 2465

Difficulty: Medium

Paid? No

Companies: Google, Meta, Veritas

Problem Description

Given a string s and a 2D integer array shifts, where each element in shifts is of the form [start, end, direction], you must shift the characters in s from index start to end (inclusive). A direction value of 1 indicates a forward shift (to the next character in the alphabet, wrapping around from 'z' to 'a'), while a value of 0 indicates a backward shift (to the previous character in the alphabet, wrapping around from 'a' to 'z'). Return the final string after applying all shift operations sequentially.

Key Insights

  • Use a difference array to accumulate the net shift effect for each index.
  • For each shift [start, end, direction], update the difference array at start and end+1 to mark where the shift influence begins and ends.
  • Compute a prefix sum on the difference array to obtain the effective shift value for each character.
  • Shift each character with modulo operations to handle wrapping around within the alphabet.

Space and Time Complexity

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

Solution

The solution uses a difference array to capture the cumulative effect of all shifting instructions. For each shift, determine the effect (+1 for a forward shift and -1 for a backward shift) and apply it to the difference array. Then, construct the final string by computing the prefix sum at every index and adjusting the original character by the computed shift. The modulo arithmetic ensures the character remains within the bounds of 'a' to 'z'.

Code Solutions

Below are code implementations in Python, JavaScript, C++, and Java with line-by-line comments.

# Python solution for Shifting Letters II

def shiftingLettersII(s, shifts):
    n = len(s)
    # Initialize difference array with zeros, length n+1
    diff = [0] * (n + 1)
    
    # Process each shift instruction
    for start, end, direction in shifts:
        # Set shift value: -1 for backward (direction == 0), +1 for forward (direction == 1)
        value = -1 if direction == 0 else 1
        diff[start] += value
        diff[end + 1] -= value  # end+1 marks where the shift effect stops
    
    curr_shift = 0
    result = []
    # Apply prefix sum to get the net shift at each position
    for i in range(n):
        curr_shift += diff[i]
        # Calculate the new character with wrap-around using modulo 26
        new_char = chr((ord(s[i]) - ord('a') + curr_shift) % 26 + ord('a'))
        result.append(new_char)
    
    return ''.join(result)

# Example usage:
# print(shiftingLettersII("abc", [[0,1,0],[1,2,1],[0,2,1]]))
← Back to All Questions