Optimized way to Reverse a String | Leetcode Challenge #344

Problem Statement

Write a function that reverse a string. Input string will be given as an array of characters char[].

Can you to it without allocating extra space for another array?

Hint: You must do this by modifying the input array in-place with O(1) extra memory.

You may assume that all the characters comprise of printable ascii character.

Examples:

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

Let’s see how to solve this question.

We will use two pointers. One pointer for starting character and another one for ending character. Replace each other’s correspondent value in the character array.

For that you need 2 variables, left and right. Left variable should start from 0 (starting of array) and right index will start from end of the array.

Now loop the array till left is less than right, then swap the characters in left and right index by incrementing the left index and decrement the right.

Initially left index will be 0, and right will be end index of array which is 4. Swap the characters at left and right index.

Let’s take the 1st example of “hello”.

Now, increment the left index and decrement the right index and swap the characters. We will do this step till left is not greater than right.

1st iteration: left = ‘h’ and right = ‘0’, swapping it will result in ‘oellh’
2nd iteration: left = ‘e’ and right = ‘l’, swapping it will result in ‘olleh’.

Loop will terminate after second iteration because in third iteration doesn’t satisfy criteria left index < right

These steps will return a reverse array.

The Time Complexity of this array is O(N), and Space Complexity is O(1).

Code in Java

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

Code in Python

s = "PickupBrain Always Stay Ahead"
words = s.split(' ') 
string =[] 
for word in words: 
    string.insert(0, word) 
  
print("Reversed String is:") 
print(" ".join(string)) 


>>>Output:
Reversed String is:
Ahead Stay Always PickupBrain

Code in C#

using System; 
public class ReverseWords { 
  
    public static void Main() 
    { 
        string[] s = "PickupBrain Always Stay Ahead".Split(' '); 
        string a = ""; 
        for (int i = s.Length - 1; i >= 0; i--) { 
            a += s[i] + " "; 
        } 
        Console.Write("Reversed String is:\n"); 
        Console.Write(a.Substring(0, a.Length - 1)); 
    } 
} 


>>>Output:
Reversed String is:
Ahead Stay Always PickupBrain

Summary

The above algorithm provides the optimum solution for reversing string. It has a time complexity of O(N) since time required linearly depends on length of string and space complexity is O(1) as we need only one extra character variable for swapping. Extra space requirement is always 1 and is independent of size of character array needed to swap.