Reverse String easy

Problem Statement

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"]

Steps:

1. Two Pointers: We'll use two pointers, left and right, initially pointing to the beginning and end of the string, respectively.

2. Swap: We swap the characters at the left and right pointers.

3. Move Pointers: We increment left and decrement right, moving towards the center of the string.

4. Termination: The process continues until the left pointer crosses the right pointer (or they become equal). This ensures that the entire string is reversed.

Explanation:

The algorithm uses a simple in-place reversal technique. By using two pointers and swapping characters, we avoid creating a new string, thus fulfilling the O(1) extra memory requirement. The pointers effectively work from both ends of the string, gradually swapping characters until the middle is reached.

Code:

def reverseString(s):
    """
    Reverses a string in-place.

    Args:
      s: A list of characters.
    """
    left = 0
    right = len(s) - 1

    while left < right:
        s[left], s[right] = s[right], s[left]  # Swap characters
        left += 1
        right -= 1

# Example usage
s1 = ["h","e","l","l","o"]
reverseString(s1)
print(s1)  # Output: ['o', 'l', 'l', 'e', 'h']

s2 = ["H","a","n","n","a","h"]
reverseString(s2)
print(s2)  # Output: ['h', 'a', 'n', 'n', 'a', 'H']

Complexity:

• Time Complexity: O(N), where N is the length of the string. We iterate through approximately half the string.
• Space Complexity: O(1). We use only a constant amount of extra space (for the left and right pointers).