Reverse String (LC 344)

Pattern: Two Pointers
Difficulty: Easy
Key Concept: Swap characters symmetrically from both ends until pointers meet; char[] is mutable, so this is true O(1) extra space.

Problem Statement

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

Constraints: You must do it in-place with O(1) extra memory.

Input: char[] s (mutable array of characters).
Output: s modified so its order is reversed (often void return type).

Example: s = ['h','e','l','l','o'] → ['o','l','l','e','h'].

---

1. Algorithm & Pseudocode

Brute force (violates O(1) extra — for contrast)

1. Create a new char[] t of the same length as s.
2. For i from 0 to n-1:
     t[i] = s[n - 1 - i]
3. Copy t back into s (or return t if the API allowed — but then you'd still use O(n) space).

This shows the “reverse into a new buffer” idea. It uses O(n) auxiliary space, so it does not meet the problem’s memory requirement.

Optimal (two pointers, in-place swap)

1. left = 0, right = length(s) - 1.
2. While left < right:
     swap s[left] and s[right]
     left++, right--
3. Done.

---

2. Step-by-Step Analysis (Beginner-Friendly)

Why char[] and not String?
In Java, a String is immutable: you cannot reverse it without creating a new String. The problem gives a char[] so you can swap elements in place, which satisfies O(1) extra memory (only index variables and maybe one temp char).

Why two pointers?
Reversing means the first character swaps with the last, the second with the second-last, and so on. Two pointers implement exactly half the array’s worth of swaps.

How many swaps?
About n / 2. When n is odd, the middle character stays put.

C++ analogy
You might take string& s and swap in place. Java passes the reference to the char[] object; swaps inside the method mutate the same array the caller holds.

StringBuilder.reverse()
Handy for StringBuilder, but the problem’s contract is char[] in-place—so the interview answer is the two-pointer swap on the array.

---

3. The Dry Run

Sample: s = ['h','e','l','l','o']
Indices: 0..4, length n = 5.

Step	left	right	s before swap	Swap pair	s after swap
init	0	4	h e l l o	—	—
1	0	4	h e l l o	s[0]↔s[4] (h,o)	o e l l h
2	1	3	o e l l h	s[1]↔s[3] (e,l)	o l l e h
3	2	2	o l l e h	left < right is false → stop	—

Middle element: index 2 ('l') never moves—correct for odd length.

Even-length example (mental check): ['a','b'] → one swap → ['b','a'].

---

4. Java Solution

Brute Force

Idea: New char[] reversed copy, then copy back. Does not satisfy O(1) extra (shown for learning).

• Time: O(n)
• Space: O(n) auxiliary

class Solution {
    public void reverseString(char[] s) {
        int n = s.length;
        char[] t = new char[n];
        for (int i = 0; i < n; i++) {
            t[i] = s[n - 1 - i];
        }
        System.arraycopy(t, 0, s, 0, n);
    }
}

Optimal

Idea: Symmetric swaps from both ends.

• Time: O(n)
• Space: O(1) (only indices + temp char)

class Solution {
    public void reverseString(char[] s) {
        int left = 0;
        int right = s.length - 1;
        while (left < right) {
            char tmp = s[left];
            s[left] = s[right];
            s[right] = tmp;
            left++;
            right--;
        }
    }
}

---

5. The “Java vs. Others” Edge

• char[] is mutable; String is not—this problem is explicitly about array mutation.
• Java passes object references by value: the method gets a copy of the reference, but it still points at the same char[] in the heap—so swaps affect the caller’s array.
• In C++, void reverse(string& s) is the direct analogue; be careful with char* length.
• StringBuilder.reverse() solves a different API (mutable character sequence, but not the required char[] in-place signature for this exact problem statement).

---

6. Complexity Summary

Approach	Time	Space	Notes
Brute Force	O(n)	O(n)	Extra buffer; fails strict O(1) extra memory
Optimal	O(n)	O(1)	Two-pointer swaps; meets problem constraints