Leetcode 344. Reverse String

Problem

Leetcode 344 - Reverse String

Example:

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

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

Approach

Since we want to reverse the list with $O(1)$ memory, we can simply have a left and right pointer where left = 0, and right = len(s)-1. Then we can reverse these two element then increment the left, and decremetn the right pointer until left < right.

Visualization of the Approach:

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

swap s[l] and s[r] then increment l and decrement r
s = ["o","e","l","l","h"]
          l       r

swap s[l] and s[r] then increment l and decrement r
s = ["o","l","l","e","h"]
             l,r

Since l == r, we can return the s 
s = ["o","l","l","e","h"]

Here is the Python code for the solution:

class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        left, right = 0, len(s)-1

        while left < right:
            # swapping left and right element
            s[left], s[right] = s[right], s[left]
            left += 1
            right -= 1
    

Time Complexity and Space Complexity

Time Complexity: $O(n)$

Space Complexity: $O(1)$