Reverse String easy

Problem Statement

Write a function that reverses a string. The input string is given as an array of characters s. You must do this by modifying the input array in-place with O(1) extra memory.

Example 1:

Input: s = ["h","e","l","l","o"] Output: ["o","l","l","e","h"]

Example 2:

Input: s = ["H","a","n","n","a","h"] Output: ["h","a","n","n","a","H"]

Steps:

1. Two Pointers: We'll use two pointers, left and right, initially pointing to the beginning and end of the array, respectively.

2. Swap: We swap the characters at the left and right pointers.

3. Move Pointers: We increment left and decrement right, moving towards the center of the array.

4. Termination: We continue swapping and moving pointers until left and right cross each other (left >= right). This ensures that we've processed the entire array.

Explanation:

The algorithm uses a simple in-place reversal technique. By using two pointers and swapping elements, we avoid creating a new array, thus fulfilling the O(1) extra memory constraint. The two-pointer approach efficiently iterates through the array, performing the reversal in a single pass. The loop condition left < right guarantees that the entire string is reversed without unnecessary iterations.

Code:

function reverseString(s: string[]): void {
    let left = 0;
    let right = s.length - 1;

    while (left < right) {
        // Swap characters at left and right pointers
        [s[left], s[right]] = [s[right], s[left]];

        // Move pointers towards the center
        left++;
        right--;
    }
};

Complexity:

• Time Complexity: O(N), where N is the length of the string. We iterate through the array once.
• Space Complexity: O(1). We use a constant amount of extra space for the pointers, regardless of the input size. The in-place modification ensures we don't create a new array.