Problem Description

The "Reverse Only Letters" problem asks you to reverse only the letters in a given string S, while keeping all non-letter characters in their original positions. For example, if the input string contains numbers, dashes, or other symbols, those should stay in the same index, and only the alphabetic characters should be reversed in order.

Key Constraints:

• The input string S consists of only printable ASCII characters.
• All non-letter characters must remain in their original positions.
• Only letters (both uppercase and lowercase) are reversed.
• There is exactly one valid output for each input string.

Thought Process

At first glance, it may seem like simply reversing the string would work. However, because non-letter characters must stay in their original places, a direct reversal will not produce the correct result.

The brute-force approach would involve extracting all the letters, reversing them, and then reconstructing the string by placing the reversed letters back into the original positions, skipping over the non-letter characters. However, this method requires extra space and multiple passes through the string.

To optimize, we can use the two-pointer technique: one pointer starts from the beginning, and another from the end. Both pointers move towards each other, skipping non-letter characters. When both pointers point to letters, we swap them. This approach is more efficient and intuitive, as it allows us to reverse only the letters in a single pass with minimal extra space.

Solution Approach

We use the two-pointer approach to solve the problem efficiently:

1. Initialize two pointers:
   • left starts at the beginning of the string (index 0).
   • right starts at the end of the string (index len(S) - 1).
2. Iterate until left is less than right:
   • If S[left] is not a letter, move left forward.
   • If S[right] is not a letter, move right backward.
   • If both S[left] and S[right] are letters, swap them and move both pointers towards the center.
3. Continue until the pointers meet or cross.
4. Return the modified string.

This method ensures that all non-letter characters remain in their original positions, and only the letters are reversed in place. The approach is efficient because it only requires a single pass through the string and uses constant extra space (aside from converting the string to a list for in-place modification, if needed).

Example Walkthrough

Input: S = "a-bC-dEf-ghIj"

Let's follow the two-pointer approach step-by-step:

1. Start: left = 0 ('a'), right = 11 ('j').
2. Both are letters, swap: 'a' ↔ 'j'. Now, string is "j-bC-dEf-ghIa". Move left to 1, right to 10.
3. S[1] is '-' (not a letter), increment left to 2.
4. S[10] is 'I' (letter), so now left = 2 ('b'), right = 10 ('I').
5. Both are letters, swap: 'b' ↔ 'I'. Now, string is "j-IC-dEf-ghba". Move left to 3, right to 9.
6. Continue this process, skipping non-letters and swapping letters at each step.
7. Final output after all swaps: "j-Ih-gfE-dCba"

Notice how all dashes and non-letter characters remain in their original positions, and the sequence of letters is reversed.

Time and Space Complexity

Brute-force Approach:

• Time Complexity: O(N) for extracting letters, O(N) for reconstructing the string. Overall, O(N).
• Space Complexity: O(N) extra space for storing letters.

• Time Complexity: O(N), where N is the length of the string. Each character is visited at most once.
• Space Complexity: O(N) if converting string to a list (since strings are immutable in some languages), but O(1) extra space if in-place modification is allowed.

The two-pointer approach is optimal because it minimizes both time and space usage, making only a single pass through the string and requiring no additional data structures beyond the input itself.

Summary

The "Reverse Only Letters" problem is a great example of using the two-pointer technique to efficiently reverse elements in a string under specific constraints. By carefully handling non-letter characters and only swapping letters, we achieve a solution that is both simple and optimal. The two-pointer approach is elegant because it avoids unnecessary extra space and keeps the logic straightforward, making it easy to implement and understand.

Code Implementation

class Solution:
    def reverseOnlyLetters(self, S: str) -> str:
        chars = list(S)
        left, right = 0, len(chars) - 1
        while left < right:
            if not chars[left].isalpha():
                left += 1
            elif not chars[right].isalpha():
                right -= 1
            else:
                chars[left], chars[right] = chars[right], chars[left]
                left += 1
                right -= 1
        return ''.join(chars)
      

class Solution {
public:
    string reverseOnlyLetters(string S) {
        int left = 0, right = S.size() - 1;
        while (left < right) {
            if (!isalpha(S[left])) {
                ++left;
            } else if (!isalpha(S[right])) {
                --right;
            } else {
                swap(S[left], S[right]);
                ++left;
                --right;
            }
        }
        return S;
    }
};
      

class Solution {
    public String reverseOnlyLetters(String S) {
        char[] chars = S.toCharArray();
        int left = 0, right = chars.length - 1;
        while (left < right) {
            if (!Character.isLetter(chars[left])) {
                left++;
            } else if (!Character.isLetter(chars[right])) {
                right--;
            } else {
                char temp = chars[left];
                chars[left] = chars[right];
                chars[right] = temp;
                left++;
                right--;
            }
        }
        return new String(chars);
    }
}
      

var reverseOnlyLetters = function(S) {
    let chars = S.split('');
    let left = 0, right = chars.length - 1;
    while (left < right) {
        if (!(/[a-zA-Z]/).test(chars[left])) {
            left++;
        } else if (!(/[a-zA-Z]/).test(chars[right])) {
            right--;
        } else {
            let temp = chars[left];
            chars[left] = chars[right];
            chars[right] = temp;
            left++;
            right--;
        }
    }
    return chars.join('');
};