344. Reverse String

Description

The problem requires reversing a string, represented as an array of characters, in-place. We need to swap the characters without using additional memory for another array. The goal is to reverse the input array with minimal space complexity.

Intuition

Reversing a string can be visualized as swapping the first character with the last, the second character with the second-to-last, and so on, until the entire array is reversed. By using two pointers, one starting from the beginning and the other from the end, we can efficiently swap elements and reduce the number of operations.

Approach

1. Initialize two pointers: i at the beginning of the array and j at the end.
2. Swap the elements at positions i and j.
3. Increment i and decrement j to move towards the center of the array.
4. Continue swapping until the two pointers meet or cross each other, indicating that the entire array has been reversed.
5. This process runs in-place, so no additional memory is needed beyond the input array.

Complexity

Time Complexity:

O(n), where n is the length of the array. Each character is swapped once, and we traverse half the array due to the two-pointer approach.

Space Complexity:

O(1), since we only use a constant amount of extra space for the two pointers and the temporary variable during swapping.

Code

C++

class Solution {
public:
    void reverseString(vector& s) {
        int i = 0, j = s.size() - 1;
        while (i < j) {
            char temp = s[i];
            s[i] = s[j];
            s[j] = temp;
            i++;
            j--;
        }
    }
};

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 += 1
            j -= 1

Java

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

JavaScript

/**
 * @param {character[]} s
 * @return {void} Do not return anything, modify d in-place instead.
 */
var reverseString = function(d) {
    let j = d.length - 1 , i = 0;
    while(i < j){
        const Lle = d[i];
        d[i] = d[j]
        d[j] = Lle;
        j--;
        i++;
    }

};