Sweaty Imposter

Reverse String

EasyTwo PointersNeetCode 150JuniorOpen on LeetCodeUpdated

You're given a string as an array of characters s. Reverse the order of the characters in place, so the first character becomes the last and so on. Don't return anything and don't build a new array: modify s directly using only O(1) extra memory.

Examples

s = ["h","e","l","l","o"] returns ["o","l","l","e","h"]

The first and last characters trade places, then the second and fourth. The middle "l" stays where it is.

s = ["H","a","n","n","a","h"] returns ["h","a","n","n","a","H"]

The capital "H" and the lowercase "h" swap ends. The inner letters "anna" read the same backwards, so they look unchanged.

Constraints

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

Hints

Hint 1

The first character has to end up last, and the last one first. Which pairs of positions need to trade?

Hint 2
A pointer toward the approach
Hint 3
The full approach, step by step

Drill This: Your Approach First

Approach

Reversing means character i trades places with character n - 1 - i. Put left at the start and right at the end, swap s[left] and s[right], then move both inward. Stop when they meet or cross: by then every pair has been swapped once, and the middle character of an odd-length array stays put. Only two index variables are used.

Time

O(n)

Space

O(1)

Pitfall

Swapping across the whole array instead of stopping at the middle swaps every pair twice and restores the original order. In Python, s = s[::-1] only rebinds the local name and leaves the caller's list unchanged.

Solutions

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