Shifting Letters II

Medium

Google

3 views

Topics:

ArraysStrings

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

Write a function to efficiently compute the final string after applying all shifts.

Shifting Letters II

Medium

Google

3 views

Topics:

ArraysStrings

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

Write a function to efficiently compute the final string after applying all shifts.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

Can the input string `s` contain characters other than lowercase English letters?
Are the start and end indices in the `shifts` array inclusive or exclusive?
Can the `shifts` array be empty? What should I return in that case?
Can the shift values in the `shifts` array be very large, potentially leading to integer overflow if applied directly and repeatedly?
If, after a series of shifts, a letter goes beyond 'z' or before 'a', should it wrap around (e.g., 'z' shifted by 1 becomes 'a', and 'a' shifted by -1 becomes 'z')?

Brute Force Solution

Approach

The brute force method modifies a word letter by letter according to instructions. For each instruction, we go through the specified portion of the word and shift the letters as directed, handling letter wrapping as needed.

Here's how the algorithm would work step-by-step:

Start with the original word.
Take the first instruction: identify the section of the word that needs to be modified according to the start and end points in the instruction.
For each letter in that section, change it by shifting it forward or backward in the alphabet, as indicated by the direction of the instruction.
If shifting goes past 'a' or 'z', wrap around to the other end of the alphabet (like a circle).
After changing all the letters in the section according to the first instruction, move on to the next instruction.
Repeat the process of identifying the section of the word and shifting the letters for each remaining instruction.
Once all instructions have been applied, the modified word is the result.

Code Implementation

def shifting_letters_two_brute_force(word, shifts):
    modified_word = list(word)

    for shift_instruction in shifts:
        start_index = shift_instruction[0]
        end_index = shift_instruction[1]
        shift_direction = shift_instruction[2]

        # Iterate over the section to be modified.
        for index in range(start_index, end_index + 1):
            original_character = modified_word[index]
            original_ascii_value = ord(original_character)

            # Apply the shift based on the specified direction.
            if shift_direction == 1:
                new_ascii_value = original_ascii_value + 1
                if new_ascii_value > ord('z'):
                    new_ascii_value = ord('a')
            else:
                new_ascii_value = original_ascii_value - 1

                # Wrap around if we go past 'a'.
                if new_ascii_value < ord('a'):
                    new_ascii_value = ord('z')

            modified_word[index] = chr(new_ascii_value)

    return "".join(modified_word)

Big(O) Analysis

Time Complexity

O(n*m) – The algorithm iterates through the given list of m shift instructions. For each instruction, it iterates through a portion of the input string of length n. In the worst case, each shift instruction affects the entire string. Therefore, the time complexity is proportional to the product of the number of instructions (m) and the length of the string (n), resulting in O(n*m). Note that if m is proportional to n, then the time complexity would become O(n^2).

Space Complexity

O(1) – The algorithm modifies the input word in-place. It iterates through instructions, and for each instruction modifies a portion of the word. No auxiliary data structures of significant size (relative to the input) are created. Therefore, the extra space used is constant, irrespective of the word length or the number of instructions.

Optimal Solution

Approach

We need to modify a string of letters based on a series of shifts. Instead of applying each shift individually, which would be slow, we can calculate the total shift for each letter and then apply it all at once. This dramatically reduces the number of operations.

Here's how the algorithm would work step-by-step:

First, imagine that each letter in the word has a counter that starts at zero. This counter will represent the total amount each letter will be shifted.
Go through each shifting instruction. For each instruction, add to the counters of the letters that need to be shifted. If the instruction is a forward shift, increment the counters. If it's a backward shift, decrement the counters.
Now, use the counters we've built to actually shift the letters in the original word. For each letter, take its counter value and shift the letter that amount forward or backward in the alphabet.
If shifting a letter goes past 'z' or before 'a', wrap around the alphabet so it starts from the beginning or end, respectively.
Finally, combine the shifted letters to form the final, modified string.

Code Implementation

def shiftingLetters(string, shifts):
    string_length = len(string)
    shift_values = [0] * string_length

    for start, end, direction in shifts:
        shift_direction = 1 if direction == 1 else -1

        shift_values[start] += shift_direction
        if end + 1 < string_length:
            shift_values[end + 1] -= shift_direction

    cumulative_shift = 0
    shifted_string = list(string)

    # Accumulate shift values to get net shift
    for index in range(string_length):
        cumulative_shift += shift_values[index]
        
        # Apply shifting to each letter
        original_char_code = ord(string[index]) - ord('a')
        new_char_code = (original_char_code + cumulative_shift) % 26

        # Wrapping logic implemented here.
        if new_char_code < 0:
            new_char_code += 26

        shifted_string[index] = chr(new_char_code + ord('a'))

    return "".join(shifted_string)

Big(O) Analysis

Time Complexity

O(n + m) – The solution iterates through the input string `s` of length `n` and the shifts array of length `m`. The first loop iterates through the `shifts` array to update the shift counts for each character. The second loop iterates through the string `s` to apply the calculated shifts. Therefore, the time complexity is dominated by these two loops, resulting in O(n + m) where n is the length of the string and m is the length of the shift array.

Space Complexity

O(N) – The algorithm creates an auxiliary array (the 'counters' array in step 1) to store the total shift for each letter in the input string, where N is the length of the input string. The size of this array is directly proportional to the length of the input string. No other significant data structures are created, so the space used is dominated by this counters array, leading to a space complexity of O(N).

Edge Cases

Case	How to Handle
Null or empty string s	Return an empty string or throw an exception, depending on requirements; the provided operations array is not applicable.
Null or empty operations array	Return the original string since no shifts are specified.
Empty operations within the operations array	Skip the empty operation (treat as a no-op) or raise an exception, depending on problem constraints.
Large operations array size exceeding memory limits	Consider using an in-place modification of the string or a more memory-efficient data structure.
Start index equals end index in an operation	The substring affected by this operation is just a single character, so apply the shift directly.
Start index greater than end index in an operation	Treat this as an invalid input and either throw an error or swap start and end, depending on the expected behavior.
Absolute value of shift is extremely large causing integer overflow	Use modulo operation with 26 to constrain the shift value within the alphabet range.
Operations overlap, causing multiple shifts to the same character	Accumulate all the shifts for each character, then apply a single cumulative shift modulo 26 to each character at the end.