algoadvance

The task is to 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.

Clarifying Questions

1. Input Constraints:
   • What is the length range of the input array s?
     • It can be up to 10^5 characters.
   • What types of characters can be in the array?
     • The array can contain any printable ASCII characters.
2. Function Signature:
   • The function signature is defined as: def reverseString(s: List[str]) -> None:
   • It does not return anything; the input array should be modified in-place.

Strategy

To reverse the string in-place with O(1) extra space:

1. Use the two-pointer technique:
   • Initialize one pointer at the start (left) and the other at the end (right) of the array.
   • Swap the elements at these pointers.
   • Move both pointers toward the center (increment the left pointer and decrement the right pointer).
   • Continue this process until the pointers meet or cross each other.

Code

Here’s how you can implement this in Python:

from typing import List

def reverseString(s: List[str]) -> None:
    left, right = 0, len(s) - 1
    while left < right:
        # Swap characters
        s[left], s[right] = s[right], s[left]
        # Move pointers
        left, right = left + 1, right - 1

Time Complexity

• Time Complexity: O(n)
  • We traverse the string only once, swapping elements in place.
• Space Complexity: O(1)
  • No extra space is used; the reversal is done in-place.

Explanation:

1. Initialization:
   • Set left pointer to the start (0th index).
   • Set right pointer to the end (last index).
2. Swapping Elements:
   • Swap the elements at positions left and right.
   • Increment left and decrement right.
3. Termination:
   • The loop terminates when left is no longer less than right.

Example Walkthrough:

Consider s = ["h", "e", "l", "l", "o"]:

1. Initial state:

   left = 0, right = 4
   ["h", "e", "l", "l", "o"]
   

2. First iteration:

   Swap s[0] and s[4]:
   ["o", "e", "l", "l", "h"]
   Move pointers: left = 1, right = 3
   

3. Second iteration:

   Swap s[1] and s[3]:
   ["o", "l", "l", "e", "h"]
   Move pointers: left = 2, right = 2
   

4. End condition:

   Since left is not less than right, stop
   Final state: ["o", "l", "l", "e", "h"]
   

The elements are now reversed in-place.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?