Reverse String

Difficulty: Easy

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 with O(1) extra memory. Solve it using recursion.

Example

Input: s = ["h","e","l","l","o"]
Output: ["o","l","l","e","h"]
Explanation: The array is reversed in-place.

Brute-force approach

This is a recursion-focused problem. We go directly to the recursive solution using the Leap of Faith approach.

Time complexity: - · Space complexity: -

Optimal approach

Key insight: If someone magically reverses the inner portion of the array for you, all you need to do is swap the outermost pair. That's it!

Use the Leap of Faith recipe: swap the outermost pair, then trust recursion to reverse the inner portion. Two pointers (left, right) move inward with each call.

Steps

1. Call helper(s, 0, s.length - 1)
2. Base case: if left >= right, return
3. Swap s[left] and s[right]
4. Leap of Faith: helper(s, left + 1, right - 1)

Time complexity: O(n) · Space complexity: O(n)