Description

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:

1 <= s.length <= 10^5

s[i] is a printable ascii character.

Solution

This is yet another two pointer problem. In this case, we can use constant space. In order to exchange two values, we just need one additional variable to store value temporarily. The same concept can be applied. We can use two pointers, one from the left and another from right. The algorithm will look like this.

1initialize left = 0, right = array.length - 1
2while left is less than right
3    exchange array[left] with array[right]
4    increment left
5    decrement right

The java code for above algorithm would look like this.

 1class Solution {
 2    public void reverseString(char[] s) {
 3        if (s == null || s.length == 0)
 4            return;
 5        int left = 0, right = s.length - 1;
 6        while (left < right) {
 7            char temp = s[right];
 8            s[right] = s[left];
 9            s[left] = temp;
10            left++;
11            right--;
12        }
13    }
14}
  • Time Complexity: O(n)
  • Space Complexity: O(1)