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.

Examples

Example 1

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

Explanation : The given string is s = "hello" and after reversing it becomes s = "olleh".

Example 2

Input : s = ["b", "y" ,"e" ]
Output : ["e", "y", "b"]

Explanation : The given string is s = "bye" and after reversing it becomes s = "eyb".

Constraints

1 <= s.length <= 105
s consist of only lowercase and uppercase English characters.

Approaches

1️⃣ Swapping Beginning and End of String

Intuition:

To reverse a string, another method is swapping the characters from the beginning and end simultaneously. This can be achieved using two pointers: one positioned at the leftmost character and the other at the rightmost character. Swap these two characters and then move both the pointers toward the center until they meet. In this manner, the first character is swapped with the last, the second with the second last, and so forth.

Approach:

1. Set up two pointers: i and j.Initialize the pointer i to 0 (the start of the string) and j to (length of string - 1) (the end of the string).
2. Use a while loop to iterate as long as i is less than j and in each iteration, swap the characters at positions i and j.
3. After swapping, increment i by 1 and decrement j by 1. Continue this process until the pointers meet or cross each other.

Code:

#include <iostream>
#include <vector>

class Solution {	
public:		
    std::vector<char> reverseString(std::vector<char>& s) {
        int i = 0; // Initialize pointer i to the start of the string
        int j = s.size() - 1; // Initialize pointer j to the end of the string

        while (i < j) {
            // Swap the characters at i and j
            std::swap(s[i], s[j]);
            i++; // Move i towards the center
            j--; // Move j towards the center
        }
        return s;
    }
};

int main() {
    Solution solution;
    std::vector<char> str = {'h', 'e', 'l', 'l', 'o'}; // Example string
    std::vector<char> reversedStr = solution.reverseString(str); // Reverse the string

    for (char c : reversedStr) {
        std::cout << c; // Print each character of the reversed string
    }
    std::cout << std::endl; // New line after the output
    return 0;
}

Complexity Analysis:

• Time Complexity O(N) - Linear time complexity, where n is the length of the string. The algorithm iterates through half of the string.
• Space Complexity O(1) - Constant space complexity. The algorithm only uses a few extra variables regardless of the input size.

Note: This same approach can also be implemented using recursion. Recursively, the function can swap the characters at the two ends of the string and then call itself for the substring excluding these ends until the string is reversed.