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

Number: 878

Difficulty: Medium

Paid? No

Companies: Google, Bloomberg

Problem Description

Given a string s and an integer array shifts of the same length, for each shifts[i] we shift the first i+1 letters of s by x times (cyclically advancing each letter). The task is to compute and return the final string after applying all shifts.

Key Insights

  • Shifting a letter means moving to the next letter in the alphabet with wrap-around from 'z' to 'a'.
  • Instead of applying shifts from the beginning each time, it is efficient to process the shifts in reverse order to compute cumulative shifts.
  • Using a running suffix sum allows us to know how much each letter should ultimately be shifted.
  • Modulo operation is key since shifting 26 times results in the same letter.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the string, because we traverse the array once. Space Complexity: O(n) if creating a new array for the output. It can be optimized to O(1) additional space if updating in place (excluding the output).

Solution

We solve the problem using a reverse traversal of the shifts array to accumulate the total shifts for each character. By iterating from the end index towards the beginning, we compute a running total. As we process each character, we apply the shift modulo 26 (the number of letters in the alphabet) and update the character accordingly. This method avoids the repeated shifting of the same prefix and makes the solution efficient.

Code Solutions

# Python solution for Shifting Letters
def shiftingLetters(s, shifts):
    n = len(s)
    # Create a list from string s to modify characters in place.
    s_list = list(s)
    total_shift = 0
    
    # Process shifts in reverse order
    for i in range(n - 1, -1, -1):
        total_shift += shifts[i]            # accumulate current shift into total_shift
        total_shift %= 26                   # take modulo 26 to wrap around after 'z'
        
        # Calculate new character after shifting
        original_index = ord(s_list[i]) - ord('a')  # convert character to 0-indexed number (0 for 'a')
        new_index = (original_index + total_shift) % 26  # add total_shift and wrap using modulo
        s_list[i] = chr(new_index + ord('a'))         # convert number back to character
        
    # Join list to form the final shifted string
    return "".join(s_list)

# Example usage:
#print(shiftingLetters("abc", [3, 5, 9]))  # Output: "rpl"
← Back to All Questions