Shifting Letters II

You are given a string s of lowercase English letters and a 2D integer array shifts where shifts[i] = [start<sub>i</sub>, end<sub>i</sub>, direction<sub>i</sub>]. For every i, shift the characters in s from the index start<sub>i</sub> to the index end<sub>i</sub> (inclusive) forward if direction<sub>i</sub> = 1, or shift the characters backward if direction<sub>i</sub> = 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".

def shifting_letters(s: str, shifts: list[list[int]]) -> str:
    """Applies a series of shifts to a string and returns the final string.

    Args:
        s: The input string of lowercase English letters.
        shifts: A 2D array where each element is [start_i, end_i, direction_i].
                direction_i = 1 means shift forward, direction_i = 0 means shift backward.

    Returns:
        The final string after applying all shifts.
    """

    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

        original_char_code = ord(s[i])
        new_char_code = original_char_code + shift_val

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

        result_char = chr(new_char_code)
        result.append(result_char)

    return "".join(result)


# Example Usage and Tests:

# Example 1
s = "abc"
shifts = [[0, 1, 0], [1, 2, 1], [0, 2, 1]]
print(f"Input: s = '{s}', shifts = {shifts}")
print(f"Output: {shifting_letters(s, shifts)}")  # Output: ace

# Example 2
s = "dztz"
shifts = [[0, 0, 0], [1, 1, 1]]
print(f"Input: s = '{s}', shifts = {shifts}")
print(f"Output: {shifting_letters(s, shifts)}")  # Output: catz

# Test case with empty shifts
s = "abc"
shifts = []
print(f"Input: s = '{s}', shifts = {shifts}")
print(f"Output: {shifting_letters(s, shifts)}")  # Output: abc

# Test case with a single shift
s = "abc"
shifts = [[0, 2, 1]]
print(f"Input: s = '{s}', shifts = {shifts}")
print(f"Output: {shifting_letters(s, shifts)}")  # Output: bcd

# Test case with wrapping around z to a
s = "xyz"
shifts = [[0, 2, 1]]
print(f"Input: s = '{s}', shifts = {shifts}")
print(f"Output: {shifting_letters(s, shifts)}")  # Output: yza

# Test case with wrapping around a to z
s = "abc"
shifts = [[0, 2, 0]]
print(f"Input: s = '{s}', shifts = {shifts}")
print(f"Output: {shifting_letters(s, shifts)}")  # Output: zab

#Test case that contains forward and backward
s = "zcza"
shifts = [[0,3,0],[1,2,1]]
print(f"Input: s = '{s}', shifts = {shifts}")
print(f"Output: {shifting_letters(s, shifts)}")

Explanation:

The problem requires shifting characters in a string s based on a series of shifts defined in the shifts array. Each shift consists of a start index, an end index, and a direction (forward or backward). The goal is to return the modified string after applying all shifts.

Approach:

1. Difference Array: Instead of directly modifying the string for each shift, we use a difference array diff to record the net shift for each index. For each shift operation, we increment diff[start] by 1 (for forward shift) or -1 (for backward shift) and decrement diff[end + 1] by 1 or -1, respectively. This allows us to accumulate the total shift for each index efficiently.

2. Prefix Sum: After processing all shifts, we compute the prefix sum of the diff array. The prefix sum at each index represents the total shift value for the corresponding character in the string.

3. Character Shifting: We iterate through the string s and for each character, we calculate the new character code by adding the shift value (prefix sum) to the original character code. We handle wraparound cases where the new character code goes beyond 'z' or before 'a' by adding or subtracting 26, respectively.

4. String Construction: Finally, we construct the modified string by converting the new character codes back to characters and joining them.

Time and Space Complexity:

• Time Complexity: O(n + m), where n is the length of the string s and m is the number of shifts in the shifts array. This is because we iterate through the shifts array once (O(m)) and then iterate through the string once (O(n)).
• Space Complexity: O(n), where n is the length of the string s. This is because we use the diff array of size n + 1 to store the differences.

Edge Cases:

• Empty shifts array: If the shifts array is empty, the function should return the original string without any modifications.
• Single shift: If the shifts array contains only one shift, the function should apply only that shift to the specified range of characters.
• Wraparound: The function should correctly handle cases where shifting a character forward results in a character beyond 'z' or shifting a character backward results in a character before 'a'. It should wrap around to 'a' or 'z', respectively.
• Start and end indices: The function should correctly handle cases where start and end indices are the same, or when they are at the boundaries of the string.
• Combination of forward and backward shifts: The function should work correctly with a mix of forward and backward shifts, ensuring that the net shift is correctly calculated and applied to each character.