# Reverse String
**Difficulty:** EASY
[External](https://leetcode.com/problems/reverse-string)
Canonical: https://scaleengineer.com/dsa/problems/reverse-string
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers)
**Data structures:** String
**Companies:** [Deutsche Bank](https://scaleengineer.com/companies/deutsche-bank), [EPAM Systems](https://scaleengineer.com/companies/epam-systems), [Garmin](https://scaleengineer.com/companies/garmin), [Goldman Sachs](https://scaleengineer.com/companies/goldman-sachs), [HCL](https://scaleengineer.com/companies/hcl), [Infosys](https://scaleengineer.com/companies/infosys), [Morgan Stanley](https://scaleengineer.com/companies/morgan-stanley), [tcs](https://scaleengineer.com/companies/tcs), [Odoo](https://scaleengineer.com/companies/odoo)
---
## Problem
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](https://en.wikipedia.org/wiki/In-place%5Falgorithm) 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"]

**Constraints:**

* `1 <= s.length <= 105`
* `s[i]` is a [printable ascii character](https://en.wikipedia.org/wiki/ASCII#Printable%5Fcharacters).

# Approaches
## Recursive Approach
This approach uses recursion to swap characters from the outside in. A helper function is defined that takes two pointers, one at the start and one at the end of the current segment to be reversed. In each recursive call, it swaps the characters at these pointers and then calls itself for the inner segment.
**Time:** O(N), where N is the length of the character array. The function makes N/2 recursive calls before reaching the base case, and each call performs a constant amount of work (one swap). · **Space:** O(N), where N is the length of the string. The space complexity is determined by the depth of the recursion stack. For a string of length N, the recursion depth will be approximately N/2, leading to O(N) space usage. This does not meet the problem's constraint of O(1) extra memory.
**Pros:** The code can be very elegant and concise.; It's a good way to demonstrate an understanding of the divide-and-conquer paradigm.
**Cons:** Violates the O(1) extra space constraint due to the memory used by the recursion stack.; Can lead to a `StackOverflowError` for very large input strings.
### Explanation
The core idea is to solve the problem by breaking it down into smaller, identical subproblems. We define a function that reverses a segment of the array defined by `left` and `right` indices.

The base case for the recursion is when the `left` pointer has met or surpassed the `right` pointer. This indicates that the segment is either empty or contains a single character, which doesn't need reversal.

In the recursive step, we swap the characters at the `left` and `right` ends of the current segment. Then, we invoke the function again for the sub-array that lies between these two pointers, effectively moving inwards.

```java
class Solution {
    public void reverseString(char[] s) {
        helper(s, 0, s.length - 1);
    }

    private void helper(char[] s, int left, int right) {
        if (left >= right) {
            return;
        }
        char temp = s[left];
        s[left] = s[right];
        s[right] = temp;
        helper(s, left + 1, right - 1);
    }
}
```
### Algorithm
*   Define a helper function `helper(s, left, right)` that takes the character array and two pointers, `left` and `right`.
*   Set the base case for the recursion: if `left` is greater than or equal to `right`, it means the segment is fully reversed, so return.
*   In the recursive step, swap the characters at `s[left]` and `s[right]`.
*   Make a recursive call for the inner segment of the array: `helper(s, left + 1, right - 1)`.
*   Initiate the process from the main function by calling `helper(s, 0, s.length - 1)`.

## Two Pointers Approach
This is the optimal, in-place approach that satisfies all the problem constraints. It uses two pointers, one starting from the beginning of the array (`left`) and the other from the end (`right`). The pointers move towards each other, and at each step, the characters they point to are swapped.
**Time:** O(N), where N is the length of the character array. We iterate through approximately N/2 elements of the array to perform the swaps. This results in a linear time complexity. · **Space:** O(1). We only use a few variables (`left`, `right`, `temp`) to store pointers and for the swap. The amount of extra memory used is constant and does not depend on the size of the input array. This meets the problem's constraint.
**Pros:** Optimal time complexity of O(N).; Optimal space complexity of O(1), satisfying the in-place requirement.; Simple and easy to understand and implement.; Avoids any risk of stack overflow, making it safe for very large inputs.
**Cons:** There are no significant cons for this approach as it is the most efficient and standard solution for this problem.
### Explanation
This iterative method is the standard way to solve this problem while adhering to the memory constraint. We set up two pointers, `left` starting at index 0 and `right` at the last index. We then loop until the `left` pointer is no longer less than the `right` pointer. In each iteration, we swap the characters `s[left]` and `s[right]`. After the swap, we move `left` one step to the right and `right` one step to the left, bringing them closer to the middle. This process continues until the entire array is reversed. The loop condition `left < right` correctly handles both even and odd length arrays, ensuring the middle element (in odd-length arrays) is not moved.

```java
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 towards the center
            left++;
            right--;
        }
    }
}
```
### Algorithm
*   Initialize two pointers: `left` at the beginning of the array (index `0`) and `right` at the end of the array (index `s.length - 1`).
*   Use a `while` loop that continues as long as `left < right`.
*   Inside the loop, swap the characters at the `left` and `right` pointers using a temporary variable.
*   After the swap, move the pointers towards the center by incrementing `left` and decrementing `right`.
*   The loop terminates when the pointers meet or cross, at which point the array is fully reversed.

# Solutions
### CPP

```cpp
class Solution {
public:
  void reverseString(vector<char> &s) {
    for (int i = 0, j = s.size() - 1; i < j;) {
      swap(s[i++], s[j--]);
    }
  }
};

```

### Java

```java
class Solution {
public
  void reverseString(char[] s) {
    for (int i = 0, j = s.length - 1; i < j; ++i, --j) {
      char t = s[i];
      s[i] = s[j];
      s[j] = t;
    }
  }
}

```

### JavaScript

```javascript
/** * @param {character[]} s * @return {void} Do not return anything, modify s in-place instead. */ var reverseString =
  function (s) {
    for (let i = 0, j = s.length - 1; i < j; ++i, --j) {
      [s[i], s[j]] = [s[j], s[i]];
    }
  };

```

### Python

```python
class Solution:
    def reverseString(self, s: List[str]) -> None: """ Do not return anything, modify s in-place instead. """ s[:] = s[:: - 1]  # class Solution : def reverseString ( self , s : List [ str ]) -> None : i , j = 0 , len ( s ) - 1 while i < j : s [ i ], s [ j ] = s [ j ], s [ i ] i , j = i + 1 , j - 1

```