Reverse String

Difficulty: Easy

Problem

Write a function that flips a string end to end. The string arrives as an array of characters s, and you must rearrange that same array in place using only O(1) extra memory (no second array). Solve it using recursion.

Example

Input: s = ["w","o","r","l","d"]
Output: ["d","l","r","o","w"]
Explanation: The characters are swapped in place from the outside in: 'w' with 'd', then 'o' with 'l', leaving 'r' in the middle.

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)

Pseudocode

function reverseString(s):
    helper(s, 0, len(s) - 1)

function helper(s, left, right):
    if left >= right:
        return
    swap s[left] and s[right]
    helper(s, left + 1, right - 1)

Hints

  • What is the simplest array that's already reversed? (Base case: 0 or 1 element)
  • If someone magically reverses the inner portion, what's left to do? (Swap the outermost pair!)
  • Two pointers: left and right move inward with each recursive call

Complexity questions

What is the time complexity of the recursive reversal?

O(n). We make n/2 recursive calls, each doing O(1) work (one swap). Total: O(n/2) = O(n).

What is the space complexity (call stack)?

O(n). The recursion goes n/2 levels deep. Each frame uses constant space. Total stack space: O(n/2) = O(n).

How many swaps does reversing a 6-element array require?

3. floor(6/2) = 3 swaps: (index 0↔5), (index 1↔4), (index 2↔3). Each recursive call handles one pair.

Check your understanding of Reverse String

If someone magically reverses the inner portion [e, l, l] of [h, e, l, l, o] to get [h, l, l, e, o], what do you still need to do?

Swap h and o (the outermost pair). That's the Leap of Faith! Trust the recursion to handle the inner portion. You just swap the outermost pair (h ↔ o). Together: [o, l, l, e, h]. Done!

What is the base case for recursive reversal?

When left >= right (0 or 1 elements left). When left >= right, there are 0 or 1 elements in the subproblem, already 'reversed' by definition. No swap needed!

How many swaps does reversing a 5-element array require?

2. We swap pairs from outside in: (index 0 ↔ 4) and (index 1 ↔ 3). The middle element stays. That's floor(n/2) = 2 swaps.

Related problems

Keep practising