Solution Explanation: Reversing a String in-place

The problem asks to reverse a string represented as a character array in-place with O(1) extra space. The most efficient approach is using two pointers.

Algorithm:

1. Initialization: Set two pointers, left and right. left starts at the beginning of the array (index 0), and right starts at the end of the array (index length - 1).

2. Iteration: While left is less than right:

   • Swap the characters at indices left and right.
   • Increment left and decrement right, moving the pointers towards the middle of the array.

3. Termination: The loop continues until left and right cross each other (left >= right). At this point, the string is reversed.

Time Complexity: O(n), where n is the length of the string. We iterate through approximately half the string, swapping elements.

Space Complexity: O(1). We use only a constant amount of extra space for the pointers; no auxiliary data structures are needed. The reversal happens directly within the input array.

Code Examples:

The provided code snippets demonstrate this algorithm in various programming languages. Let's analyze a few:

Python:

class Solution:
    def reverseString(self, s: List[str]) -> None:
        i, j = 0, len(s) - 1
        while i < j:
            s[i], s[j] = s[j], s[i]
            i, j = i + 1, j - 1

This Python code directly implements the two-pointer approach. The while i < j condition ensures the loop terminates when the pointers meet in the middle. Python's tuple assignment (s[i], s[j] = s[j], s[i]) efficiently performs the swap in-place.

Java:

class Solution {
    public void reverseString(char[] s) {
        for (int i = 0, j = s.length - 1; i < j; ++i, --j) {
            char t = s[i];
            s[i] = s[j];
            s[j] = t;
        }
    }
}

The Java code is very similar, using a for loop for conciseness. A temporary variable t is used for swapping to avoid potential data loss during the simultaneous assignment.

Other Languages:

The other languages (C++, Go, TypeScript, Rust, JavaScript) showcase the same fundamental algorithm with minor syntactic variations. They all maintain the O(n) time and O(1) space complexity. The key is the in-place swapping using two pointers converging from the ends towards the middle of the array.