Problem Statement


Write a function that reverses a string. The input string is given as an array of characters char[].

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

You may assume all the characters consist of printable ascii characters.

 

Example 1:
Input: ["h","e","l","l","o"]
Output: ["o","l","l","e","h"]

Example 2:
Input: ["H","a","n","n","a","h"]
Output: ["h","a","n","n","a","H"]

Solution Explanation

This problem is very simple and often asked on phone screen interviews. In this problem, we have to reverse a string which is given as an array of characters.

We can always think of solving it by doing brute force but we are told not to allocate space for another array. So how about we solve this question by iterative swapping using two pointers? let's start one pointer, pointing at start of string and second pointer , pointing at end of the string. Both pointers will keep swapping characters which they are pointing to and move forward towards each other until both pointers meet. At this point, we have met midpoint which means, we reversed the string.


class Solution {
    public void reverseString(char[] s) {
        int i = 0, j = s.length -1;
        while(i < j){
            char ch = s[i];
            s[i] = s[j];
            s[j] = ch;
            i++;j--;
        }
        
    }
}

Time Complexity

We are visiting each elements in the given array, so time complexity is going to be , O(n) which is  linear runtime.

Space Complexity

We have not allocated any extra space to store data so our space complexity is going to be, O(1).