Reverse String

LeetCode Problem #344 (Easy)

Problem Statement

Write a function that reverses a string. The input string is given as an array of characters char[].

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

You may assume all the characters consist of printable ASCII characters.

Testcases

Example 1:

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

Example 2:

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

Prerequisite Knowledge

Swapping using a Temporary Variable

To swap elements in place, we can make use of a temporary variable.

// Initialize a temporary variable
int temp;
// Assign one value to the temporary value
temp = arr[i];
// Swap the value with the required value
arr[i] = arr[j];
/*
Retrieve the value of the first element from the temporary variable.
Assign the value to the element which has been swapped
*/  
arr[j] = temp;

Algorithm

Swap Characters Approach

In this approach, we simply swap the characters from either end of the character array which would ultimately produce a reversed version of the original array.

1. Calculate the length of the array and store it in a variable.

2. Initialize two pointers to point to the extreme ends of the array.

3. Traverse the array and swap the elements at the left and right positions, using a temporary variable.

4. When the left and right pointers become equal or break the condition (left < right), stop.

Space Complexity: O(1)

Code

void reverseString(vector<char>& s) {
    // Store the size of the vector in a variable
    int len = s.size();
    // Initialize a left and right pointer to point to the extreme ends of the vector
    int left = 0, right = len - 1;
    // Declare a temporary variable to store the characters to be swapped in each iteration
    char temp;
    
    // End the loop when the condition (left < right) breaks
    while(left < right) {
        // Swap the letters in the left and right positions
        temp = s[left];
        s[left] = s[right];
        s[right] = temp;
        // Increment the left pointer and decrement the right pointer
        left++;
        right--;
    }
}