Introduction

In this blog post, we will explore how to solve the LeetCode problem "2381" 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 a 2D integer array shifts where shifts[i] = [starti, endi, directioni]. For every i, shift the characters in s from the index starti to the index endi (inclusive) forward if directioni = 1, or shift the characters backward if directioni = 0. Shifting a character forward means replacing it with the next letter in the alphabet (wrapping around so that 'z' becomes 'a'). Similarly, shifting a character backward means replacing it with the previous letter in the alphabet (wrapping around so that 'a' becomes 'z'). Return the final string after all such shifts to s are applied. Example 1: Input: s = "abc", shifts = [[0,1,0],[1,2,1],[0,2,1]] Output: "ace" Explanation: Firstly, shift the characters from index 0 to index 1 backward. Now s = "zac". Secondly, shift the characters from index 1 to index 2 forward. Now s = "zbd". Finally, shift the characters from index 0 to index 2 forward. Now s = "ace". Example 2: Input: s = "dztz", shifts = [[0,0,0],[1,1,1]] Output: "catz" Explanation: Firstly, shift the characters from index 0 to index 0 backward. Now s = "cztz". Finally, shift the characters from index 1 to index 1 forward. Now s = "catz". Constraints: 1 <= s.length, shifts.length <= 5 * 104 shifts[i].length == 3 0 <= starti <= endi < s.length 0 <= directioni <= 1 s consists of lowercase English letters.

Explanation

Here's the solution:

• Differential Array: Utilize a differential array (or prefix sum array) to efficiently track the net shift applied to each character in the string. Increment the shift value at the start index and decrement it at the end index + 1.
• Prefix Sum: Calculate the prefix sum of the differential array. This provides the total shift value for each index in the string.

• Apply Shifts: Iterate through the string, applying the calculated shifts (wrapping around 'a' and 'z') to generate the final result.

• Runtime Complexity: O(n + m), where n is the length of the string s and m is the number of shifts in shifts. Storage Complexity: O(n)

Code

    def shiftingLetters(s: str, shifts: list[list[int]]) -> str:
    n = len(s)
    diff = [0] * (n + 1)

    for start, end, direction in shifts:
        if direction == 1:
            diff[start] += 1
            diff[end + 1] -= 1
        else:
            diff[start] -= 1
            diff[end + 1] += 1

    prefix_sum = 0
    result = ""
    for i in range(n):
        prefix_sum += diff[i]
        shift_val = prefix_sum % 26

        char_code = ord(s[i]) + shift_val

        while char_code < ord('a'):
            char_code += 26
        while char_code > ord('z'):
            char_code -= 26

        result += chr(char_code)

    return result