Introduction

In this blog post, we will explore how to solve the LeetCode problem "848" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

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, shift('a') = 'b', shift('t') = 'u', and shift('z') = '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 1: Input: s = "abc", shifts = [3,5,9] Output: "rpl" Explanation: We start with "abc". After shifting the first 1 letters of s by 3, we have "dbc". After shifting the first 2 letters of s by 5, we have "igc". After shifting the first 3 letters of s by 9, we have "rpl", the answer. Example 2: Input: s = "aaa", shifts = [1,2,3] Output: "gfd" Constraints: 1 <= s.length <= 105 s consists of lowercase English letters. shifts.length == s.length 0 <= shifts[i] <= 109

Explanation

Here's an efficient solution to the problem:

• Reverse Iteration and Accumulation: Iterate through the shifts array in reverse order. Accumulate the shift values from right to left, taking the modulo 26 at each step to avoid integer overflow and keep the shift within the alphabet range.
• Character Shifting: For each character in the string s, calculate the final shift value (which is the accumulated shift at that index). Apply the shift to the character, wrapping around from 'z' to 'a' as needed.

• In-place Modification: Modify the string s in-place by converting it to a list first, and then joining the characters back into a string after all shifts are applied.

• Runtime & Storage Complexity:

  • Runtime Complexity: O(n), where n is the length of the string s.
  • Storage Complexity: O(n) because of the string to list conversion for in-place modification. Technically, this could be O(1) in some languages which support modification of immutable strings in place, but in Python it will be O(n).

Code

    def shiftingLetters(s: str, shifts: list[int]) -> str:
    n = len(s)
    shifts_total = 0
    result = list(s)

    for i in range(n - 1, -1, -1):
        shifts_total = (shifts_total + shifts[i]) % 26
        original_char_code = ord(result[i])
        shifted_char_code = (original_char_code - ord('a') + shifts_total) % 26 + ord('a')
        result[i] = chr(shifted_char_code)

    return "".join(result)