Reverse String

Difficulty: Easy | Acceptance: 80.80% | Paid: No Topics: Two Pointers, 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.

• Examples
• Constraints
• Approach 1: Two Pointers
• Approach 2: Recursion
• Approach 3: Brute Force (New Array)

Examples

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

1 <= s.length <= 10⁵
s[i] is a printable ascii character.

Approach 1: Two Pointers

Intuition Use two pointers starting from the beginning and end of the array, swapping elements until they meet in the middle.

Steps

• Initialize a left pointer at index 0 and a right pointer at the last index.
• While left is less than right, swap the characters at these pointers.
• Increment the left pointer and decrement the right pointer.

class Solution:
    def reverseString(self, s: list[str]) -> None:
        left, right = 0, len(s) - 1
        while left < right:
            s[left], s[right] = s[right], s[left]
            left += 1
            right -= 1

Complexity

• Time: O(n)
• Space: O(1)
• Notes: Most optimal solution for in-place reversal.

Approach 2: Recursion

Intuition Recursively swap the outermost characters and then process the inner substring.

Steps

• Define a helper function that takes the array and two indices.
• Base case: if the left index is greater than or equal to the right index, return.
• Swap the characters at the left and right indices.
• Recursively call the helper with left + 1 and right - 1.

class Solution:
    def reverseString(self, s: list[str]) -> None:
        def helper(left, right):
            if left >= right:
                return
            s[left], s[right] = s[right], s[left]
            helper(left + 1, right - 1)
        helper(0, len(s) - 1)

Complexity

• Time: O(n)
• Space: O(n)
• Notes: Uses stack space for recursion, which is less efficient than the iterative approach for large inputs.

Approach 3: Brute Force (New Array)

Intuition Create a new array containing the elements in reverse order, then copy them back to the original array.

Steps

• Initialize a new array of the same length.
• Iterate through the original array from the end to the beginning.
• Place each element into the new array starting from the beginning.
• Copy the new array back into the original array.

class Solution:
    def reverseString(self, s: list[str]) -> None:
        n = len(s)
        reversed_s = [0] * n
        for i in range(n):
            reversed_s[i] = s[n - 1 - i]
        for i in range(n):
            s[i] = reversed_s[i]

Complexity

• Time: O(n)
• Space: O(n)
• Notes: Violates the O(1) extra memory constraint but demonstrates a straightforward logic.