Problem Definition

LeetCode link: 344. Reverse String

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

You must do this by modifying the input array in-place with O(1) extra memory.

Example 1:

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

Example 2:

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

Constraints:

Thought Process

You may recall that we previously discussed Problem 206: Reverse Linked List, where we used the two-pointer method. The same two-pointer approach can be applied to reversing strings, but string reversal is actually simpler than linked list reversal.

206. Reverse Linked List
Master three different approaches to solving LeetCode’s Reverse Linked List problem (#206). Learn the efficient two-pointer technique, recursive method, and stack-based solution with detailed explanations and Python implementations. Perfect for coding interviews and data structure practice.
Fanyang Meng's BlogFanyang Meng

This simplicity stems from a fundamental characteristic of strings: since a string is a type of array, its elements are stored contiguously in memory. This continuous memory layout creates important differences between how we reverse linked lists versus strings.

For those who aren't fully comfortable with the underlying principles of arrays and linked lists, I recommend reviewing two foundational concepts:

Fundamentals of Linked List
Learn the fundamentals of linked lists, including types, memory storage, operations, and performance comparisons with arrays. Discover how linked lists enable dynamic memory management, allow O(1) insertions and deletions, and are ideal for handling variable-sized data with frequent modifications.
Fanyang Meng's BlogFanyang Meng

Understanding these basics will make the reversal process much clearer.

When it comes to string reversal, we employ two pointers (which can also be thought of as index positions). One pointer starts at the beginning of the string, while the other starts at the end. These pointers simultaneously move toward the center of the string, swapping elements as they go.

Key Insights

  • A two-pointer approach is ideal for this problem, as it allows for swapping elements at both ends and works in O(n) time with O(1) space.
  • While Python provides rich built-in functions like reversed() and slicing ([::-1]), these are best used for smaller problems or when simplicity is preferred.

Solution 1: Two-Pointer Technique

How It Works

The two-pointer technique is simple yet efficient. Two pointers, left and right, are initialized at the start and end of the list, respectively. In each iteration, the elements at these pointers are swapped, and the pointers move closer to the center. This process continues until the pointers meet or cross each other, ensuring the string is reversed in place.

Code Explanation

class Solution:
    def reverseString(self, s: list[str]) -> None:
        """
        Reverse the input list of characters in-place.
        """
        left, right = 0, len(s) - 1
        while left < right:
            s[left], s[right] = s[right], s[left]
            left += 1
            right -= 1

Complexity Analysis

  • Time Complexity: O(n), where n is the length of the string. Each character is visited once.
  • Space Complexity: O(1), as no additional space is allocated.

Detailed Walkthrough

For example, given ['h', 'e', 'l', 'l', 'o']:

  1. left points to 'h' and right points to 'o'. Swap them: ['o', 'e', 'l', 'l', 'h'].
  2. left moves to 'e' and right moves to 'l'. Swap them: ['o', 'l', 'l', 'e', 'h'].
  3. The pointers meet at 'l', and the process stops.

Solution 2: Using a Stack

Overview

A stack is a Last In, First Out (LIFO) structure. By pushing all characters onto a stack and then popping them off, the order is naturally reversed.

Code Explanation

class Solution:
    def reverseString(self, s: list[str]) -> None:
        """
        Reverse the input list of characters in-place.
        """
        stack = []
        for char in s:
            stack.append(char)
        for i in range(len(s)):
            s[i] = stack.pop()

Complexity Analysis

  • Time Complexity: O(n), as each character is pushed and popped once.
  • Space Complexity: O(n), due to the stack storing all characters.

Detailed Walkthrough

For example, given ['h', 'e', 'l', 'l', 'o']:

  1. Push all characters onto the stack: stack = ['h', 'e', 'l', 'l', 'o'].
  2. Pop characters off and overwrite the original list: ['o', 'l', 'l', 'e', 'h'].

Solution 3: Using Slicing

Overview

Python’s slicing syntax provides a quick way to reverse a list. The [::-1] slice reverses the list, but this approach creates a new list and overwrites the original.

Code Explanation

class Solution:
    def reverseString(self, s: list[str]) -> None:
        """
        Reverse the input list of characters in-place.
        """
        s[:] = s[::-1]

Complexity Analysis

  • Time Complexity: O(n), as slicing traverses the entire list.
  • Space Complexity: O(n), because slicing creates a new list.

Notes

While concise, this approach does not satisfy the in-place requirement for certain scenarios.

Let me explain why this approach, while elegant, doesn't fully satisfy the in-place requirement.

The key lies in understanding what happens under the hood when we use Python's slice notation s[::-1]. Let's break it down step by step:

When we write s[:] = s[::-1], two distinct operations occur:

  1. First, s[::-1] creates a new list containing all elements in reverse order:
# If s = ['h', 'e', 'l', 'l', 'o']
# s[::-1] creates a new list ['o', 'l', 'l', 'e', 'h']
  1. Then, s[:] performs a slice assignment, copying the elements from the new reversed list back into the original list's memory space:
# s[:] = ['o', 'l', 'l', 'e', 'h']
# This overwrites the original contents

The issue with true in-place operations becomes clear when we consider memory usage. During this process, Python temporarily needs enough memory to hold both:

  • The original list: ['h', 'e', 'l', 'l', 'o']
  • The reversed copy: ['o', 'l', 'l', 'e', 'h']

This means that for a string of length n, we need O(n) extra space. For small strings, this isn't a problem, but imagine working with very large strings or in memory-constrained environments:

# Consider a string with 1 million characters
s = ['a'] * 1_000_000

# Using slice notation
s[:] = s[::-1]  # Temporarily needs memory for 2 million characters!

So while the slice notation approach is more concise and perfectly fine for many practical applications, it doesn't meet the strict definition of an in-place algorithm, which requires O(1) extra space. This distinction becomes crucial in interviews or when working with systems where memory constraints are a critical consideration.

Solution 4: Using Built-In reverse()

Overview

Python lists have a built-in reverse() method that reverses the list in place. This method is efficient and straightforward.

Code Explanation

class Solution:
    def reverseString(self, s: list[str]) -> None:
        """
        Reverse the input list of characters in-place.
        """
        s.reverse()

Complexity Analysis

  • Time Complexity: O(n), as the reverse operation visits each element once.
  • Space Complexity: O(1), as the operation is performed in place.

Solution 5: Using Range Iteration

Overview

By iterating through the first half of the list, we can swap each element with its counterpart from the end. This approach is similar to the two-pointer technique but uses a range-based loop.

Code Explanation

class Solution:
    def reverseString(self, s: list[str]) -> None:
        """
        Reverse the input list of characters in-place.
        """
        n = len(s)
        for i in range(n // 2):
            s[i], s[n - i - 1] = s[n - i - 1], s[i]

Complexity Analysis

  • Time Complexity: O(n)
  • Space Complexity: O(1)

Detailed Walkthrough

The formula n-i-1 helps us find the matching position for each character we want to swap. Here's why each part is important:

  1. Start with n (length of string = 5)
  2. Subtract i (our current position from the start)
  3. Subtract 1 (because we count from 0 in programming)

Think of it like two people walking toward each other from opposite ends of a line. As one person takes a step forward from the start (i increases), the other person must take a step back from the end (subtracting i from n-1).

This creates a perfect mirroring effect:

When i = 0: partner is at n-1   (5-0-1 = 4)
When i = 1: partner is at n-2   (5-1-1 = 3)
When i = 2: partner is at n-3   (5-2-1 = 2)

Solution 6: Using List Comprehension

Overview

List comprehensions can be used to create a reversed version of the input list. While this approach is less common, it demonstrates Python’s expressive syntax.

Code Explanation

class Solution:
    def reverseString(self, s: list[str]) -> None:
        """
        Reverse the input list of characters in-place.
        """
        s[:] = [s[i] for i in range(len(s) - 1, -1, -1)]

For example, if we have the string "hello" (length 5), the range would generate:

len(s) - 1 = 4
range(4, -1, -1) generates: 4, 3, 2, 1, 0

Complexity Analysis

  • Time Complexity: O(n)
  • Space Complexity: O(n), due to the new list created.

Key Takeaways

Two-Pointer Technique (Best Solution)

  • Why It's Best:
    • Truly in-place operation (O(1) space)
    • Simple implementation
    • Optimal time complexity O(n)
    • No temporary array needed

Solution Comparison

  1. Two-Pointer/Range Solutions
    • ✅ True in-place operation
    • ✅ O(1) space complexity
    • ✅ Meets all problem requirements
    • Best choice for interviews
  2. Python Built-in Methods
    • reverse(): Good for production code
    • s[::-1]: Readable but uses O(n) space
    • Trade-off between readability and space efficiency
  3. Stack-Based Approach
    • ❌ Not truly in-place (O(n) space)
    • Useful for understanding the concept
    • Good for learning purposes
MethodSpaceTimeIn-Place?
Two-PointerO(1)O(n)Yes
Range-basedO(1)O(n)Yes
StackO(n)O(n)No
SlicingO(n)O(n)No
Built-in reverse()O(1)O(n)Yes
List ComprehensionO(n)O(n)No