Strings•Easy

Reverse String

String Reversal

Reverse String

Reversing a string is a classic algorithmic operation that flips the character order, making the first character become the last, the second become the second-to-last, and so on. For instance, reversing "HELLO" produces "OLLEH".

Implementation Mechanics: The Two Pointers Technique

The most space-efficient way to reverse a string is the Two Pointers approach, which performs the operation in-place:

  1. Pointers Placement: Place a left pointer at index 0 and a right pointer at index N - 1 (pointing to the last valid character).
  2. Character Swap: Swap the characters at arr[left] and arr[right].
  3. Pointers Update: Increment the left pointer (left++) and decrement the right pointer (right--).
  4. Terminate: Repeat steps 2 and 3 until the two pointers meet or cross in the middle (left >= right).

Note: In immutable string environments (like Java or Python), strings cannot be modified in-place. You must convert the string to a mutable character array first, reverse that array, and then convert it back to a new string object.

Complexity Analysis

  • Time Complexity:
    • Best/Worst/Average Case: O(N) (where N is the length of the string, since we perform roughly N / 2 swaps)
  • Space Complexity: O(1) (constant auxiliary space for the in-place array swap)