algoadvance

You are given a string s of lowercase English letters and an integer array shifts of the same length.

Call the shift of a letter, the next letter in the alphabet, (wrapping around so that ‘z’ becomes ‘a’).

• For example, shifting 'a' by 1 gives 'b', and shifting 'z' by 1 gives 'a'.

Now for each shifts[i] = x, we want to shift the first i + 1 letters of s, x times.

Return the final string after all such shifts to s are applied.

Example

Input: s = "abc", shifts = [3,5,9]
Output: "rpl"
Explanation: 
We start with "abc".
After shifting the first 1 letters by 3, we have "dbc".
After shifting the first 2 letters by 5, we have "igc".
After shifting the first 3 letters by 9, we have "rpl".

Constraints

• 1 <= s.length <= 10^5
• s consists of lowercase English letters.
• shifts.length == s.length
• 0 <= shifts[i] <= 10^9

Clarifying Questions

1. Does the operation of shifts on the string mutate the string?
   • Yes, continuously mutate the string according to the shifts specified in the list.
2. How to interpret shifting?
   • Shifting is taken as moving the character forward in the alphabet. For instance, shifting ‘a’ by 1 will result in ‘b’, and ‘z’ by 1 will result in ‘a’ due to wrap-around.

Strategy

1. Understand the Shift Cumulative Effect:
   • We observe that applying the shifts as specified will be computationally expensive if done directly. Instead, accumulate them in reverse order to determine the net shift effect cumulatively.
2. Implement Efficient Shifting using Modular Arithmetic:
   • Determine the effective shifts for the position by processing the shifts array in reverse.
   • Utilize modular arithmetic to map the shifts efficiently within the bounds of a-z.

Code

def shiftingLetters(s: str, shifts: List[int]) -> str:
    n = len(s)
    
    # Initialize cumulative shifts
    cumulative_shift = 0
    
    # Initialize result list of characters
    result = list(s)
    
    # Traverse shifts in reverse to accumulate the shifts
    for i in range(n - 1, -1, -1):
        cumulative_shift += shifts[i]
        cumulative_shift %= 26
        
        # Shift the i-th character
        new_char = chr((ord(s[i]) - ord('a') + cumulative_shift) % 26 + ord('a'))
        
        result[i] = new_char
    
    # Join the list into the final string
    return ''.join(result)

Time Complexity

• O(n): We are traversing the string and shifts array a constant number of times.
• The space complexity is O(n) to construct the result string.

This solution should handle the given constraints efficiently.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?