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, initialized to the beginning and end of the array, respectively.

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

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

4. Termination: The process continues until the left pointer is greater than or equal to the right pointer, indicating that we've reached the middle of the array (or processed the entire array if the length is odd).

Explanation:

The algorithm uses a two-pointer approach for efficient in-place reversal. By swapping characters from the beginning and end and moving the pointers inwards, we effectively reverse the string without needing extra space to store a reversed copy. This approach guarantees O(1) extra space complexity. The number of swaps is proportional to the length of the string divided by 2, resulting in O(n) time complexity.

Code:

class Solution {
    public void reverseString(char[] s) {
        int left = 0;
        int right = s.length - 1;

        while (left < right) {
            // Swap characters
            char temp = s[left];
            s[left] = s[right];
            s[right] = temp;

            // Move pointers
            left++;
            right--;
        }
    }
}

Complexity:

• Time Complexity: O(n), where n is the length of the string. We iterate through approximately half of the string.
• Space Complexity: O(1). We are using only a constant amount of extra space (for the left, right, and temp variables). The reversal is done in-place.