Solution Explanation: Reverse Only Letters

The problem asks to reverse only the alphabetic characters in a given string, keeping the non-alphabetic characters in their original positions. The optimal approach is using two pointers.

Algorithm:

1. Initialization:

   • Convert the input string s into a character array cs for efficient in-place modification.
   • Initialize two pointers, i (left pointer) and j (right pointer), to the beginning and end of the array respectively.

2. Iteration:

   • The while i < j loop continues as long as the left pointer is before the right pointer.

   • Inner Loops (Filtering): Two inner while loops are used to efficiently skip non-alphabetic characters:

     • The first loop increments i until it points to an alphabetic character (isalpha() or equivalent in different languages).
     • The second loop decrements j until it points to an alphabetic character.

   • Swap (if applicable): If i < j after the inner loops, it means both pointers are pointing to alphabetic characters which can be swapped. cs[i] and cs[j] are swapped. Then, i is incremented and j is decremented to move towards the middle of the string.

3. Return:

   • After the outer loop completes, the modified character array cs is joined back into a string and returned.

Time Complexity: O(n), where n is the length of the string. The algorithm iterates through the string at most once. The inner loops only skip non-alphabetic characters, not significantly affecting the overall time complexity.

Space Complexity: O(n) in the worst case. This is because we use a character array (cs) to store the modified string, which takes linear space relative to the input string length. In some languages (like C++), in-place modification could reduce space complexity to O(1), but that's not guaranteed across all languages in this solution's implementation.

Code Examples (with detailed explanations):

The provided code snippets in various programming languages implement this algorithm. Let's examine the Python code as an example:

class Solution:
    def reverseOnlyLetters(self, s: str) -> str:
        cs = list(s)  # Convert string to list for in-place modification
        i, j = 0, len(cs) - 1  # Initialize pointers
        while i < j:
            while i < j and not cs[i].isalpha(): # Skip non-alphabetic chars from left
                i += 1
            while i < j and not cs[j].isalpha(): # Skip non-alphabetic chars from right
                j -= 1
            if i < j: # Only swap if pointers haven't crossed and point to letters
                cs[i], cs[j] = cs[j], cs[i]  # Swap characters
                i, j = i + 1, j - 1  # Move pointers
        return "".join(cs) # Convert modified list back to string

The other languages (Java, C++, Go, TypeScript, Rust) follow the same algorithm structure, adapting the syntax and data structures specific to each language. isalpha() (or its equivalent) is used to check for alphabetic characters. The core logic of two pointers, inner filtering loops, and the conditional swap remains consistent across all implementations.