Jobs

Interviews

Discussions

Reverse Only Letters

Easy

Asked by:

61 views

Topics:

StringsTwo Pointers

Given a string s, reverse the string according to the following rules:

All the characters that are not English letters remain in the same position.
All the English letters (lowercase or uppercase) should be reversed.

Return s after reversing it.

Example 1:

Input: s = "ab-cd"
Output: "dc-ba"

Example 2:

Input: s = "a-bC-dEf-ghIj"
Output: "j-Ih-gfE-dCba"

Example 3:

Input: s = "Test1ng-Leet=code-Q!"
Output: "Qedo1ct-eeLg=ntse-T!"

Constraints:

1 <= s.length <= 100
s consists of characters with ASCII values in the range [33, 122].
s does not contain '\"' or '\\'.

Try coding it in LeetCode

Reverse Only Letters

Easy

Asked by:

61 views

Topics:

StringsTwo Pointers

Given a string s, reverse the string according to the following rules:

All the characters that are not English letters remain in the same position.
All the English letters (lowercase or uppercase) should be reversed.

Return s after reversing it.

Example 1:

Input: s = "ab-cd"
Output: "dc-ba"

Example 2:

Input: s = "a-bC-dEf-ghIj"
Output: "j-Ih-gfE-dCba"

Example 3:

Input: s = "Test1ng-Leet=code-Q!"
Output: "Qedo1ct-eeLg=ntse-T!"

Constraints:

1 <= s.length <= 100
s consists of characters with ASCII values in the range [33, 122].
s does not contain '\"' or '\\'.

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:

Can the input string `s` contain null or empty strings?
What is the expected range for the length of the input string `s`?
Besides standard English letters (a-z, A-Z), are there any other types of characters I should expect in the string, such as Unicode characters, numbers, or special symbols?
Should the non-letter characters maintain their exact spacing/positioning within the final reversed string?
Is case-sensitivity important for determining if a character is a letter? For example, should I treat 'a' and 'A' differently when identifying letters to reverse?

Brute Force Solution

Approach

The brute force approach to reversing only the letters in a string involves examining the string character by character. When we encounter a letter, we want to find the last letter in the string and swap them. The strategy continues by finding the next innermost pair of letters to swap until we've processed all letter pairs.

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

Examine the string from beginning to end.
If a character is a letter, search the string from the end towards the beginning to find another letter.
Once you find a pair of letters (one from the start and one from the end), swap their positions in the string.
Continue this process of finding letter pairs from the outside in, and swapping them.
Make sure to only swap letters, and leave any non-letter characters in their original positions.
Repeat until all letter pairs have been swapped, essentially reversing the order of only the letters within the string.

Code Implementation

def reverse_only_letters_brute_force(input_string):
    string_list = list(input_string)
    left_index = 0
    right_index = len(input_string) - 1

    while left_index < right_index:
        # Move left pointer until a letter is found
        while left_index < right_index and not string_list[left_index].isalpha():
            left_index += 1

        # Move right pointer until a letter is found
        while left_index < right_index and not string_list[right_index].isalpha():
            right_index -= 1

        # Ensures we only swap if both pointers are on letters
        if left_index < right_index:
            string_list[left_index], string_list[right_index] = string_list[right_index], string_list[left_index]

            left_index += 1
            right_index -= 1

    return "".join(string_list)

Big(O) Analysis

Time Complexity

O(n²) – The algorithm iterates through the string of length n. For each character, if it's a letter, it searches from the end of the string to find another letter to swap. In the worst case, for each of the potentially n letters, we might need to scan almost the entire string again to find its corresponding letter. This results in roughly n * n/2 comparisons and potential swaps, giving a time complexity of O(n²).

Space Complexity

O(N) – The described algorithm modifies the string in-place, implying it's working with a mutable string data type. However, to perform the swaps character by character as described, a common implementation would likely involve converting the string into an array of characters. If N is the length of the input string, this array would require O(N) auxiliary space. While the algorithm itself doesn't explicitly mention creating other data structures, the character array required for the swap operations dominates the space usage. Thus, the space complexity is O(N).

Optimal Solution

Approach

To efficiently reverse only the letters in a string, we use a two-ended approach. We essentially swap letters from the front and back of the string until we meet in the middle, ignoring any non-letter characters.

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

Imagine you have two pointers, one at the very beginning of the string and the other at the very end.
Move the starting pointer forward until you find a letter.
Move the ending pointer backward until you find a letter.
Now, swap the letter at the start with the letter at the end.
Move the starting pointer one step forward and the ending pointer one step backward.
Repeat the process of finding letters and swapping them until the two pointers meet or cross each other in the middle of the string. Any non-letter characters are skipped automatically.
The string is now reversed, but only the letters have been changed, leaving other characters in their original places.

Code Implementation

def reverse_only_letters(input_string):
    string_list = list(input_string)
    start_index = 0
    end_index = len(input_string) - 1

    while start_index < end_index:
        # Move start_index forward until a letter is found
        while start_index < end_index and not string_list[start_index].isalpha():
            start_index += 1

        # Move end_index backward until a letter is found
        while end_index > start_index and not string_list[end_index].isalpha():
            end_index -= 1

        # Swap the letters at start_index and end_index
        if start_index < end_index:
            string_list[start_index], string_list[end_index] = string_list[end_index], string_list[start_index]
            start_index += 1
            end_index -= 1

    return "".join(string_list)

Big(O) Analysis

Time Complexity

O(n) – The algorithm iterates through the string using two pointers, one starting from the beginning and the other from the end. In the worst-case scenario, both pointers might need to traverse the entire string to find letters, potentially visiting each character once. Therefore, the time complexity is directly proportional to the length 'n' of the input string 's', resulting in a linear time complexity of O(n).

Space Complexity

O(N) – The described two-pointer approach requires modifying the original string. Since strings in Python are immutable, converting the string to a mutable list is necessary. This results in auxiliary space proportional to the length of the input string, N, where N is the length of the input string. The space used for the two pointers themselves is constant but dominated by the auxiliary list. Therefore, the space complexity is O(N).

Edge Cases

Case	How to Handle
Null or empty input string	Return the null or empty string immediately, as there's nothing to reverse.
String containing only non-letter characters	Return the original string unchanged, as there are no letters to reverse.
String containing only letter characters	Reverse the entire string as a standard string reversal case.
String with leading and trailing non-letter characters	The two-pointer approach will automatically skip these non-letter characters at the beginning and end.
String with consecutive non-letter characters	The two-pointer approach will correctly handle consecutive non-letter characters by skipping them.
Very long string (performance considerations)	The two-pointer approach has O(n) time complexity, so it scales linearly with the string length.
String with mixed case letters	The solution treats uppercase and lowercase letters equally for the purposes of reversing only letters.
String with unicode letters	Check if the isLetter function correctly identifies unicode letters for proper reversal; otherwise extend letter identification range.

Null or empty input string

How to Handle:

Return the null or empty string immediately, as there's nothing to reverse.

String containing only non-letter characters

How to Handle:

Return the original string unchanged, as there are no letters to reverse.

String containing only letter characters

How to Handle:

Reverse the entire string as a standard string reversal case.

String with leading and trailing non-letter characters

How to Handle:

The two-pointer approach will automatically skip these non-letter characters at the beginning and end.

String with consecutive non-letter characters

How to Handle:

The two-pointer approach will correctly handle consecutive non-letter characters by skipping them.

Very long string (performance considerations)

How to Handle:

The two-pointer approach has O(n) time complexity, so it scales linearly with the string length.

String with mixed case letters

How to Handle:

The solution treats uppercase and lowercase letters equally for the purposes of reversing only letters.

String with unicode letters

How to Handle:

Check if the isLetter function correctly identifies unicode letters for proper reversal; otherwise extend letter identification range.

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 null or empty strings?
What is the expected range for the length of the input string `s`?
Besides standard English letters (a-z, A-Z), are there any other types of characters I should expect in the string, such as Unicode characters, numbers, or special symbols?
Should the non-letter characters maintain their exact spacing/positioning within the final reversed string?
Is case-sensitivity important for determining if a character is a letter? For example, should I treat 'a' and 'A' differently when identifying letters to reverse?

Brute Force Solution

Approach

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

Examine the string from beginning to end.
If a character is a letter, search the string from the end towards the beginning to find another letter.
Once you find a pair of letters (one from the start and one from the end), swap their positions in the string.
Continue this process of finding letter pairs from the outside in, and swapping them.
Make sure to only swap letters, and leave any non-letter characters in their original positions.
Repeat until all letter pairs have been swapped, essentially reversing the order of only the letters within the string.

Code Implementation

def reverse_only_letters_brute_force(input_string):
    string_list = list(input_string)
    left_index = 0
    right_index = len(input_string) - 1

    while left_index < right_index:
        # Move left pointer until a letter is found
        while left_index < right_index and not string_list[left_index].isalpha():
            left_index += 1

        # Move right pointer until a letter is found
        while left_index < right_index and not string_list[right_index].isalpha():
            right_index -= 1

        # Ensures we only swap if both pointers are on letters
        if left_index < right_index:
            string_list[left_index], string_list[right_index] = string_list[right_index], string_list[left_index]

            left_index += 1
            right_index -= 1

    return "".join(string_list)

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Imagine you have two pointers, one at the very beginning of the string and the other at the very end.
Move the starting pointer forward until you find a letter.
Move the ending pointer backward until you find a letter.
Now, swap the letter at the start with the letter at the end.
Move the starting pointer one step forward and the ending pointer one step backward.
Repeat the process of finding letters and swapping them until the two pointers meet or cross each other in the middle of the string. Any non-letter characters are skipped automatically.
The string is now reversed, but only the letters have been changed, leaving other characters in their original places.

Code Implementation

def reverse_only_letters(input_string):
    string_list = list(input_string)
    start_index = 0
    end_index = len(input_string) - 1

    while start_index < end_index:
        # Move start_index forward until a letter is found
        while start_index < end_index and not string_list[start_index].isalpha():
            start_index += 1

        # Move end_index backward until a letter is found
        while end_index > start_index and not string_list[end_index].isalpha():
            end_index -= 1

        # Swap the letters at start_index and end_index
        if start_index < end_index:
            string_list[start_index], string_list[end_index] = string_list[end_index], string_list[start_index]
            start_index += 1
            end_index -= 1

    return "".join(string_list)

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input string	Return the null or empty string immediately, as there's nothing to reverse.
String containing only non-letter characters	Return the original string unchanged, as there are no letters to reverse.
String containing only letter characters	Reverse the entire string as a standard string reversal case.
String with leading and trailing non-letter characters	The two-pointer approach will automatically skip these non-letter characters at the beginning and end.
String with consecutive non-letter characters	The two-pointer approach will correctly handle consecutive non-letter characters by skipping them.
Very long string (performance considerations)	The two-pointer approach has O(n) time complexity, so it scales linearly with the string length.
String with mixed case letters	The solution treats uppercase and lowercase letters equally for the purposes of reversing only letters.
String with unicode letters	Check if the isLetter function correctly identifies unicode letters for proper reversal; otherwise extend letter identification range.

Null or empty input string

How to Handle:

Return the null or empty string immediately, as there's nothing to reverse.

String containing only non-letter characters

How to Handle:

Return the original string unchanged, as there are no letters to reverse.

String containing only letter characters

How to Handle:

Reverse the entire string as a standard string reversal case.

String with leading and trailing non-letter characters

How to Handle:

The two-pointer approach will automatically skip these non-letter characters at the beginning and end.

String with consecutive non-letter characters

How to Handle:

The two-pointer approach will correctly handle consecutive non-letter characters by skipping them.

Very long string (performance considerations)

How to Handle:

The two-pointer approach has O(n) time complexity, so it scales linearly with the string length.

String with mixed case letters

How to Handle:

The solution treats uppercase and lowercase letters equally for the purposes of reversing only letters.

String with unicode letters

How to Handle:

Check if the isLetter function correctly identifies unicode letters for proper reversal; otherwise extend letter identification range.