Jobs

Interviews

Discussions

Shifting Letters

Medium

Asked by:

7 views

Topics:

ArraysStrings

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 <= 10⁵
s consists of lowercase English letters.
shifts.length == s.length
0 <= shifts[i] <= 10⁹

Try coding it in LeetCode

Shifting Letters

Medium

Asked by:

7 views

Topics:

ArraysStrings

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 <= 10⁵
s consists of lowercase English letters.
shifts.length == s.length
0 <= shifts[i] <= 10⁹

Try coding it in LeetCode

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:

What are the possible characters within the input string `s`, and what is the range of shift values in the `shifts` array?
What should I return if the input string `s` is empty or if the `shifts` array is empty?
How should I handle shifts that result in characters going beyond 'z' or before 'a'? Should I wrap around?
Is the length of the `shifts` array always equal to the length of the input string `s`?
Can the shift values in the `shifts` array be negative?

Brute Force Solution

Approach

The brute force approach for shifting letters means we'll try every possible combination of shifts for each letter. We'll go through each possibility, applying the shifts and checking if the final result is what we want. This is like testing every key on a lock until we find the right one.

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

Start by considering no shifts at all. Keep the original word and see if it's our answer.
Next, consider shifting just the first letter of the word. Try shifting it by one, then by two, and so on, all the way to the maximum shift amount.
Then, consider shifting the first two letters, trying every possible combination of shifts for each of them.
Continue doing this, adding one letter at a time and trying every single possible shift combination for all the letters considered so far.
After exploring all the shift combinations for each possible letter set, check if the resulting word is the desired output.
If the resulting word from a shift combination matches the desired output, then you have found your solution. If none match, then there is no solution to be found.

Code Implementation

def shifting_letters_brute_force(original_word, target_word, max_shift):
    word_length = len(original_word)

    def apply_shifts(word, shifts):
        shifted_word = list(word)
        for index, shift_value in enumerate(shifts):
            shifted_word[index] = chr(((ord(word[index]) - ord('a') + shift_value) % 26) + ord('a'))
        return "".join(shifted_word)

    # Iterate through all possible lengths of prefixes
    for prefix_length in range(word_length + 1):
        # Create a shifts array for current prefix length
        shifts = [0] * prefix_length

        while True:
            # Check if shifts make the original word into the target word.
            shifted_word = apply_shifts(original_word, shifts)

            if shifted_word == target_word:
                return shifts

            # Increment the last shift, handling carry-over
            index = prefix_length - 1
            while index >= 0:
                shifts[index] += 1

                # Carry-over if the shift exceeds the maximum
                if shifts[index] > max_shift:

                    shifts[index] = 0
                    index -= 1
                else:

                    break

            # If all shifts are back to zero, we've exhausted all combinations
            if index < 0:
                break

    # Exhausted all possibilities - no solution
    return None

Big(O) Analysis

Time Complexity

O(m^n) – The algorithm explores all possible shift combinations for each letter in the input string. Let n be the length of the input string and m be the maximum shift amount (number of possible shifts for each letter). For the first letter, we try m shifts. For the first two letters, we try m*m (m^2) combinations of shifts. This continues, until for all n letters, we are trying m*m*...*m (n times), or m^n combinations. Therefore, the time complexity is O(m^n).

Space Complexity

O(1) – The provided brute force approach primarily manipulates the input string directly. Although intermediate shifted strings are generated to check against the target, these can be done in-place or their space usage is independent of the input string's length (N). The algorithm doesn't utilize any auxiliary data structures like lists, hash maps, or recursion that scale with the input size N. Therefore, the auxiliary space complexity remains constant, denoted as O(1).

Optimal Solution

Approach

The problem asks us to shift each letter in a string by a certain amount, specified by an array of shifts. Instead of doing the shifts individually, we can calculate the cumulative shift for each letter. Then, we apply these cumulative shifts while wrapping around the alphabet.

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

First, calculate the total shift for each letter by working backwards through the shift array. This means that the shift for the last letter is just the last number in the array, the shift for the second to last letter is the sum of the last two numbers, and so on.
Since the shifts can be very large numbers, use the remainder operation (%) with 26 to keep the shifts within the range of the alphabet (0 to 25).
Now, go through each letter in the string, add its corresponding shift value (that you calculated in step 1), and again, use the remainder operation (%) with 26 to wrap around the alphabet if needed.
Finally, convert the shifted numbers back to letters by using the fact that 'a' corresponds to 0, 'b' to 1, and so on. Return the resulting string.

Code Implementation

def shifting_letters(input_string, shifts):
    string_length = len(input_string)
    cumulative_shifts = [0] * string_length

    cumulative_shifts[-1] = shifts[-1]
    # Calculate cumulative shifts from right to left
    for index in range(string_length - 2, -1, -1):
        cumulative_shifts[index] = (cumulative_shifts[index + 1] + shifts[index])

    result_string = ''
    for index in range(string_length):
        # Normalize the shift value
        shift_value = cumulative_shifts[index] % 26

        original_char_value = ord(input_string[index]) - ord('a')

        # Apply the shift and wrap around the alphabet
        new_char_value = (original_char_value + shift_value) % 26

        result_string += chr(new_char_value + ord('a'))

    return result_string

Big(O) Analysis

Time Complexity

O(n) – The first step iterates backward through the 'shifts' array of size n to calculate cumulative shifts. The second step iterates through the input string 's', also of size n, to apply these shifts and build the result. Both loops perform a constant amount of work per element. Therefore, the dominant factor is the linear traversal of the input, resulting in a time complexity of O(n).

Space Complexity

O(N) – The algorithm calculates the cumulative shift for each letter and stores these shifts in place of the original shifts array, effectively using an array of size N, where N is the number of letters in the input string. Also, the creation of the result string which is built character by character takes up N space. The intermediate calculations are done with a constant amount of memory. Therefore, the auxiliary space complexity is O(N).

Edge Cases

Case	How to Handle
Null or empty string input	Return an empty string or throw an IllegalArgumentException if null is not allowed as input
Empty shifts array	Return the original string unchanged if the shifts array is empty.
String containing non-alphabetic characters	Filter out non-alphabetic characters, throw an exception, or define a character mapping to handle them.
Large shifts value causing integer overflow	Use modulo operator (%) to wrap the shift value within the alphabet size (26).
Very long string and shifts array leading to performance issues	Optimize the shifting process using modular arithmetic to avoid unnecessary iterations.
Shifts array containing both positive and negative shifts	The solution should correctly handle both positive (forward) and negative (backward) shifts.
A single shift value exceeding the length of the alphabet	Apply the modulo operator to the shift value to ensure it remains within the valid range (0-25).
Shifts array sums to a value much larger than alphabet size	Accumulate shifts modulo 26 to avoid integer overflow and unnecessary operations.

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:

What are the possible characters within the input string `s`, and what is the range of shift values in the `shifts` array?
What should I return if the input string `s` is empty or if the `shifts` array is empty?
How should I handle shifts that result in characters going beyond 'z' or before 'a'? Should I wrap around?
Is the length of the `shifts` array always equal to the length of the input string `s`?
Can the shift values in the `shifts` array be negative?

Brute Force Solution

Approach

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

Start by considering no shifts at all. Keep the original word and see if it's our answer.
Next, consider shifting just the first letter of the word. Try shifting it by one, then by two, and so on, all the way to the maximum shift amount.
Then, consider shifting the first two letters, trying every possible combination of shifts for each of them.
Continue doing this, adding one letter at a time and trying every single possible shift combination for all the letters considered so far.
After exploring all the shift combinations for each possible letter set, check if the resulting word is the desired output.
If the resulting word from a shift combination matches the desired output, then you have found your solution. If none match, then there is no solution to be found.

Code Implementation

def shifting_letters_brute_force(original_word, target_word, max_shift):
    word_length = len(original_word)

    def apply_shifts(word, shifts):
        shifted_word = list(word)
        for index, shift_value in enumerate(shifts):
            shifted_word[index] = chr(((ord(word[index]) - ord('a') + shift_value) % 26) + ord('a'))
        return "".join(shifted_word)

    # Iterate through all possible lengths of prefixes
    for prefix_length in range(word_length + 1):
        # Create a shifts array for current prefix length
        shifts = [0] * prefix_length

        while True:
            # Check if shifts make the original word into the target word.
            shifted_word = apply_shifts(original_word, shifts)

            if shifted_word == target_word:
                return shifts

            # Increment the last shift, handling carry-over
            index = prefix_length - 1
            while index >= 0:
                shifts[index] += 1

                # Carry-over if the shift exceeds the maximum
                if shifts[index] > max_shift:

                    shifts[index] = 0
                    index -= 1
                else:

                    break

            # If all shifts are back to zero, we've exhausted all combinations
            if index < 0:
                break

    # Exhausted all possibilities - no solution
    return None

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

First, calculate the total shift for each letter by working backwards through the shift array. This means that the shift for the last letter is just the last number in the array, the shift for the second to last letter is the sum of the last two numbers, and so on.
Since the shifts can be very large numbers, use the remainder operation (%) with 26 to keep the shifts within the range of the alphabet (0 to 25).
Now, go through each letter in the string, add its corresponding shift value (that you calculated in step 1), and again, use the remainder operation (%) with 26 to wrap around the alphabet if needed.
Finally, convert the shifted numbers back to letters by using the fact that 'a' corresponds to 0, 'b' to 1, and so on. Return the resulting string.

Code Implementation

def shifting_letters(input_string, shifts):
    string_length = len(input_string)
    cumulative_shifts = [0] * string_length

    cumulative_shifts[-1] = shifts[-1]
    # Calculate cumulative shifts from right to left
    for index in range(string_length - 2, -1, -1):
        cumulative_shifts[index] = (cumulative_shifts[index + 1] + shifts[index])

    result_string = ''
    for index in range(string_length):
        # Normalize the shift value
        shift_value = cumulative_shifts[index] % 26

        original_char_value = ord(input_string[index]) - ord('a')

        # Apply the shift and wrap around the alphabet
        new_char_value = (original_char_value + shift_value) % 26

        result_string += chr(new_char_value + ord('a'))

    return result_string

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty string input	Return an empty string or throw an IllegalArgumentException if null is not allowed as input
Empty shifts array	Return the original string unchanged if the shifts array is empty.
String containing non-alphabetic characters	Filter out non-alphabetic characters, throw an exception, or define a character mapping to handle them.
Large shifts value causing integer overflow	Use modulo operator (%) to wrap the shift value within the alphabet size (26).
Very long string and shifts array leading to performance issues	Optimize the shifting process using modular arithmetic to avoid unnecessary iterations.
Shifts array containing both positive and negative shifts	The solution should correctly handle both positive (forward) and negative (backward) shifts.
A single shift value exceeding the length of the alphabet	Apply the modulo operator to the shift value to ensure it remains within the valid range (0-25).
Shifts array sums to a value much larger than alphabet size	Accumulate shifts modulo 26 to avoid integer overflow and unnecessary operations.