# Reverse String
# Links
Get the code & notes on
# Problem Description
Write a function that reverses a string. The input string is given as an array of characters s.
# Examples
Ex 1) Input: s = ["h", "e", "l", "l", "o"]
Ex 2) Input: s = ["H", "a", "n", "n", "a", "h"]
# Constraints
s[i] is a printable ASCII character.
Do not allocate extra space for another array. You must do this in-place with O(1) extra memory.
# What is a printable ASCII Character?
ASCII stands for American Standard Code for Information Interchange and it consists of 33 non-printable and 95 printable characters.
You can check out the non-printable, printable, and extended ASCII characters here (opens new window).
For this problem we only care about the printable ASCII characters.
# What does In-Place Mean?
In-place refers to an algorithm that transforms input using no auxiliary data structure.
So, we cannot allocate extra space for another array, a hash table, or any other data structure.
Another way of saying this is we must use O(1) extra memory.
# Thought Process
Let's take our two examples from earlier and find a way to model the reversing of the characters in s.
Let's start with Ex 1)
- Initially, we have
and after reversing s our output should be:
To perform the reversal we need to swap the characters in s.
We can start by swapping the leftmost character and the rightmost character.
Then we'll move to the second leftmost character and the second rightmost character and swap them.
We'll continue this process until every character has been swapped if we have an even number of characters, or until we have one unswapped character left if we have an odd number of characters.
To perform this swapping we'll need to loop over s while there are still characters that can be swapped.
Let's visualize this process to help us see how the swapping will occur and to better understand what we need to keep track of.
1st Iteration:
Current Leftmost Character: h
Current Rightmost Character: o
Now, we can swap the characters by assigning s[0] to be s[4], but if we want to assign s[4] to be s[0], then we must first store s[0] in a temp variable.
Storing s[0] in a temp variable will allow us to still have the original character that was stored in s[0].
Here's the steps for the swapping process:
- Here's s after the 1st swap:
2nd Iteration:
Current Leftmost Character: e
Current Rightmost Character: l
Now, we can swap the characters by assigning s[1] to be s[3] and by assinging s[3] to be s[1] using the swapping process from before.
Here's the steps for the swapping process:
- Here's s after the 2nd swap:
- There are no unswapped characters left to swap with our only remaining unswapped character, s[2], so the reversal is complete.
To perform these swaps we had to keep track of the index of our current leftmost character which we'll denote with i and the index of our current rightmost character which we'll denote with j.
Keeping track of the current leftmost index required us to start with i = 0 and to increment i on each subsequent iteration.
Keeping track of the current rightmost index required us to start with j = s.length - 1 and to decrement j on each subsequent iteration.
We continued the loop while i < j.
Let's now look at Ex 2)
- Initially, we have
and after reversing s our output should be:
We need to swap the characters in s again like in Ex) 1.
Let's visualize this process to help us see how the swapping will occur for this example:
1st Iteration:
Current Leftmost Character: H
Current Rightmost Character: h
Now, we can swap the characters by assigning s[0] to be s[5] and by assinging s[5] to be s[0] using the swapping process from before.
Here's the steps for the swapping process:
- Here's s after the 1st swap:
2nd Iteration:
Current Leftmost Character: a
Current Rightmost Character: a
Now, we can swap the characters by assigning s[1] to be s[4] and by assinging s[4] to be s[1] using the swapping process from before.
Here's the steps for the swapping process:
- Here's s after the 2nd swap:
Note if you wanted to you could include a check to see if the characters are the same before swapping since the result after swapping will be the same.
3rd Iteration:
Current Leftmost Character: n
Current Rightmost Character: n
Now, we can swap the characters by assigning s[2] to be s[3] and by assinging s[3] to be s[2] using the swapping process from before.
Here's the steps for the swapping process:
- Here's s after the 3rd swap:
- Every character has been swapped, so the reversal is complete.
Notice again we continued the loop while i < j.
Using the model we described above we can come up with the following implementation:
# Implementation
var reverseString = function(s) {
let temp;
let i = 0;
let j = s.length - 1;
while (i < j) {
temp = s[i];
s[i] = s[j];
s[j] = temp;
i++;
j--;
}
};
// Case 1: s has an odd length
s = ['h', 'e', 'l', 'l', 'o'];
reverseString(s);
console.log(s);
// Case 2: s has an even length
s = ['H', 'a', 'n', 'n', 'a', 'h'];
reverseString(s);
console.log(s);