Skip to main content
CodePeetCodePeet
CodePeet 250

Reverse String

EASYProblemSolveExternal Links

Description

Write a function that reverses a string. The input string is given as an array of characters s.

You must reverse the array in-place, meaning you modify the original array directly without creating a new one. Your solution must use only O(1) extra memory — no auxiliary arrays, no new strings, just a constant number of temporary variables.

The result should have the first character swapped with the last, the second character swapped with the second-to-last, and so on, until the entire array is reversed.

Examples

Example 1

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

Output: ["o", "l", "l", "e", "h"]

Explanation: The first character 'h' moves to the last position and the last character 'o' moves to the first position. Similarly, 'e' and 'l' swap positions. The middle character 'l' stays in place because it is its own mirror.

Example 2

Input: s = ["H", "a", "n", "n", "a", "h"]

Output: ["h", "a", "n", "n", "a", "H"]

Explanation: This is an even-length string. Every character has a distinct mirror partner. 'H' and 'h' swap (first ↔ last), the two 'a' characters swap (second ↔ fifth), and the two 'n' characters swap (third ↔ fourth). Notice that case matters — 'H' and 'h' are different characters.

Example 3

Input: s = ["A"]

Output: ["A"]

Explanation: A single-character string is already its own reverse. No changes are needed.

Constraints

  • 1 ≤ s.length ≤ 10^5
  • s[i] is a printable ASCII character

Editorial

Brute Force

Intuition

The simplest way to reverse a string is to create a brand new array, fill it with the characters in reverse order, and then copy everything back into the original array.

Imagine you have a row of books on a shelf. Instead of rearranging them directly, you take out all the books one by one starting from the right end and place them on a second shelf from left to right. Once done, you move all the books from the second shelf back to the original shelf. The books are now in reverse order.

This approach is straightforward and easy to understand, but it requires an entire extra array of size n, violating the O(1) space constraint. It serves as a useful starting point to understand what the reversal should look like before optimizing.

Step-by-Step Explanation

Let's trace through with s = ["h", "e", "l", "l", "o"]:

Step 1: Create a temporary array of the same size: temp = ["", "", "", "", ""]

Step 2: Copy s[4]='o' to temp[0]. temp = ["o", "", "", "", ""]

Step 3: Copy s[3]='l' to temp[1]. temp = ["o", "l", "", "", ""]

Step 4: Copy s[2]='l' to temp[2]. temp = ["o", "l", "l", "", ""]

Step 5: Copy s[1]='e' to temp[3]. temp = ["o", "l", "l", "e", ""]

Step 6: Copy s[0]='h' to temp[4]. temp = ["o", "l", "l", "e", "h"]

Step 7: Copy temp back to s. s = ["o", "l", "l", "e", "h"]

The reversal is complete, but we used an entire extra array.

Brute Force — Reverse via Temporary Array — Watch how each character is copied from the original array to a temporary array in reverse order, then copied back.

Algorithm

  1. Create a temporary array temp of size n
  2. For i from 0 to n-1:
    • Set temp[i] = s[n - 1 - i]
  3. For i from 0 to n-1:
    • Set s[i] = temp[i]
  4. The array s is now reversed

Code

class Solution {
public:
    void reverseString(vector<char>& s) {
        int n = s.size();
        vector<char> temp(n);
        
        // Copy in reverse order
        for (int i = 0; i < n; i++) {
            temp[i] = s[n - 1 - i];
        }
        
        // Copy back
        for (int i = 0; i < n; i++) {
            s[i] = temp[i];
        }
    }
};
class Solution:
    def reverseString(self, s: list[str]) -> None:
        n = len(s)
        temp = [''] * n
        
        # Copy in reverse order
        for i in range(n):
            temp[i] = s[n - 1 - i]
        
        # Copy back
        for i in range(n):
            s[i] = temp[i]
class Solution {
    public void reverseString(char[] s) {
        int n = s.length;
        char[] temp = new char[n];
        
        // Copy in reverse order
        for (int i = 0; i < n; i++) {
            temp[i] = s[n - 1 - i];
        }
        
        // Copy back
        for (int i = 0; i < n; i++) {
            s[i] = temp[i];
        }
    }
}

Complexity Analysis

Time Complexity: O(n)

We traverse the array twice — once to copy elements into the temporary array in reverse order, and once to copy them back. Each traversal is O(n), giving O(n) + O(n) = O(n) total.

Space Complexity: O(n)

We create a temporary array of size n to hold the reversed copy. This is the entire extra space used, which violates the O(1) space constraint specified in the problem.

Why This Approach Is Not Efficient

While the brute force achieves O(n) time, it uses O(n) extra space for the temporary array. The problem explicitly requires O(1) extra memory.

The fundamental waste is creating a complete copy of the data when we only need to rearrange it. The key observation is that reversing a string is really just a series of swaps: swap the first and last elements, swap the second and second-to-last, and so on. Each swap only needs a single temporary variable (to hold one value during the exchange), not an entire array.

This leads us to the two-pointer technique: place one pointer at the beginning and one at the end, swap the elements they point to, then move both pointers inward until they meet in the middle.

Optimal Approach - Two Pointers

Intuition

Reversing a string in-place is beautifully simple when you realize that a reversed string is just the original with symmetric pairs swapped. The character at position 0 should swap with the character at position n-1. The character at position 1 swaps with position n-2. And so on.

Picture two people standing at opposite ends of a line of chairs, each holding a colored card. They walk toward each other, and every time they face a new pair of chairs, they exchange the cards on those chairs. When they meet in the middle, every card has been swapped with its mirror partner.

We use two pointers:

  • left starts at index 0 (the beginning)
  • right starts at index n-1 (the end)

At each step, swap the characters at left and right, then move both pointers one step closer to the center. Stop when the pointers cross or meet. This performs exactly n/2 swaps, visiting each pair once.

Step-by-Step Explanation

Let's trace through with s = ["h", "e", "l", "l", "o"]:

Step 1: Initialize left=0, right=4.

  • s = ['h', 'e', 'l', 'l', 'o']

Step 2: Swap s[0] and s[4]: 'h' ↔ 'o'.

  • s = ['o', 'e', 'l', 'l', 'h']

Step 3: Move pointers: left=1, right=3.

Step 4: Swap s[1] and s[3]: 'e' ↔ 'l'.

  • s = ['o', 'l', 'l', 'e', 'h']

Step 5: Move pointers: left=2, right=2.

Step 6: left (2) is no longer less than right (2). Stop. The middle character 'l' at index 2 stays in place.

Result: s = ['o', 'l', 'l', 'e', 'h']. Reversed with only 2 swaps and O(1) extra space.

Two Pointers — Converging Swap from Both Ends — Watch two pointers start at opposite ends of the array and walk toward each other, swapping mirror-image pairs at each step until they meet in the middle.

Algorithm

  1. Initialize two pointers: left = 0, right = n - 1
  2. While left < right:
    a. Swap s[left] and s[right]
    b. Increment left by 1
    c. Decrement right by 1
  3. The array is now reversed in-place

Code

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--;
        }
    }
};
class Solution:
    def reverseString(self, s: list[str]) -> None:
        left = 0
        right = len(s) - 1
        
        while left < right:
            s[left], s[right] = s[right], s[left]
            left += 1
            right -= 1
class Solution {
    public void reverseString(char[] s) {
        int left = 0;
        int right = s.length - 1;
        
        while (left < right) {
            char temp = s[left];
            s[left] = s[right];
            s[right] = temp;
            left++;
            right--;
        }
    }
}

Complexity Analysis

Time Complexity: O(n)

The two pointers start at opposite ends and move toward each other, meeting in the middle after n/2 iterations. Each iteration performs one swap (a constant-time operation). So the total work is n/2 swaps, which is O(n).

Space Complexity: O(1)

We only use two integer variables (left and right) and one temporary variable for the swap. This is constant space regardless of the input size, satisfying the O(1) extra memory requirement.