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: Initialize two pointers, left and right, pointing to the beginning and end of the string, respectively.

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

3. Move Pointers: Increment left and decrement right.

4. Repeat: Continue steps 2 and 3 until left and right pointers cross each other (or become equal). This ensures that the entire string is reversed.

Explanation

The algorithm uses a simple two-pointer approach for in-place string reversal. By swapping characters from the beginning and end and moving the pointers inwards, we efficiently reverse the string without needing any extra space proportional to the string's length. The in-place modification directly alters the original input array.

Code

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

class Solution {
public:
    void reverseString(vector<char>& s) {
        int left = 0;
        int right = s.size() - 1;

        while (left < right) {
            swap(s[left], s[right]);
            left++;
            right--;
        }
    }
};

int main() {
    vector<char> s1 = {'h', 'e', 'l', 'l', 'o'};
    Solution().reverseString(s1);
    for (char c : s1) {
        cout << c << " ";
    }
    cout << endl; // Output: o l l e h 

    vector<char> s2 = {'H', 'a', 'n', 'n', 'a', 'h'};
    Solution().reverseString(s2);
    for (char c : s2) {
        cout << c << " ";
    }
    cout << endl; // Output: h a n n a H

    return 0;
}

Complexity

• Time Complexity: O(N), where N is the length of the string. We iterate through roughly half the string.
• Space Complexity: O(1). The algorithm uses a constant amount of extra space regardless of the input size. The swap operation is performed in-place.