The Reverse String problem involves taking a given string of characters and reversing the order of the characters. This problem, despite its simplicity, invites many advanced approaches, such iteration, recursion, or multiple pointers, each presenting a unique time and space complexity tradeoff.
Write a program to reverse the given string. The program's output would be a string with all characters in reverse order.
Input: "hello world" Output: "dlrow olleh"
Input: "aba" Output: "aba"
Input: "ab" Output: "ba"
Input: "" Output: ""
Constraints
The number of characters in the string would be in the range [0, 100000].
The most straightforward answer is to use an inbuilt library-provided function that is usually available in most languages. But the interviewer is probably not interested in our knowledge of library functions. This means the ideal solution would be similar to how a library would implement a reverse
function (i.e., Python, JavaScript, Ruby). There are several approaches, and we'll discuss some of them here.
The original string's first character turns into the reverse string's last character. The second character of the original string becomes the second last character of the reversed string. And so on.
We can loop through each character of the original string and build the reversed string iteratively. We start with an empty string and append the characters to it as we loop across the original string. Please note that we are appending the characters to the beginning of the string. By doing so, we ensure that the characters appearing later in the original string appear earlier in the reversed string.
reversed_string
.reversed_string
.reversed_string
.function reverseString(string) {
let reversedString = "";
for (char of string) {
reversedString = char + reversedString;
}
return reversedString;
}
1function reverseString(string) {
2 let reversedString = "";
3 for (char of string) {
4 reversedString = char + reversedString;
5 }
6 return reversedString;
7}
Let's assume that there are n
characters in the given string.
Time Complexity: O(n²)
. A common mistake is to think of the time complexity of this approach as O(n)
, but this is not the case. The time complexity is O(n²)
because each time we append a character to the end of the string, we end up creating a new string. This new string then gets assigned to the variable reversed_string
. This is an O(n)
operation, and we are doing this for each character in the string. So the total time complexity is O(n * n) = O(n²)
.
If we are coding in a language that support string mutability, then appending a character would be a constant time operation. So the time complexity would be O(n)
.
Space Complexity: O(n)
. We are creating a new string of length n
, which is the only memory space we use.
In the previous approach, we noted that it was not the optimal solution because we were creating a new string each time we added a character to the end of the string, which is an O(n)
operation. Can we find a way to bring this operation down to O(1)
?
Instead of creating a new string every time we need to find a data structure that we can append individual characters to in constant time, and to this we can use a stack. A stack is a data structure that follows the LIFO principle. In this approach, we push all the characters of the original string onto the stack and then pop them one by one in order to build the reversed string.
Additionally, while building the reversed string, we use a dynamic array to store the characters. By using a dynamic array, we avoid creating a new string every time we append a character to the end of the string, making the operation O(1)
instead of O(n)
.
stack
.reversed_string
.reversed_string
.reversed_string
and return it.function reverseString(string) {
let stack = [];
for (char of string) {
stack.push(char);
}
let reversedString = [];
while (stack.length > 0) {
reversedString.push(stack.pop());
}
return reversedString.join("");
}
1function reverseString(string) {
2 let stack = [];
3 for (char of string) {
4 stack.push(char);
5 }
6 let reversedString = [];
7 while (stack.length > 0) {
8 reversedString.push(stack.pop());
9 }
10 return reversedString.join("");
11}
Let's assume that there are n
characters in the given string.
Time Complexity: O(n)
. We are looping through the original string once and pushing the characters to the stack. Then we loop across the string again and pop all the characters from the stack. Finally, we join all the characters of reversed_string, so the total time complexity is O(n + n + n) = O(3n) = O(n)
Please note that an algorithm that takes 3n
time is classified with O(n)
time complexity. Big-O notation is a measure of how an algorithm scales as the size of the input grows. As the size of n
increases, the constant factor 3
becomes insignificant.
Space Complexity: O(n)
, as we use a stack that stores n
characters.
When a string is reversed, the last character becomes the first character, and the first character becomes the last character. Similarly, the second last character becomes the second character, and the second character becomes the second last character. And so on. In other words, characters at the same position relative to the start and the end of the string are swapped.
We iterated from one end of the string to the other in the previous approaches. It is also possible to iterate from both ends of the string simultaneously. Let's have two pointers, one pointing at the start of the string and the other at the end of the string. We can swap the characters at these two pointers. Then we can move the pointers toward the middle of the string. We can keep doing this until the two pointers meet each other.
In most languages, a string is immutable. This means that we cannot change the characters of the string. We can only create a new string. So we need to convert the string to a character array. Then we can swap the characters at the two pointers. After swapping all the characters, we can transform the character array back to a string.
If the language supports mutable strings (e.g., Ruby, PHP, Swift), we can directly swap the characters at the two pointers. Some languages don't support mutability directly, but might have a class or a standard library that provides a mutable string. For example, there is StringBuilder in Java.
char_array
.start
and end
, to point at the start and the end of the string, respectively.start
is less than end
.start
and end
.start
and decrement end
.function reverseString(string) {
let charArray = string.split("");
let start = 0;
let end = charArray.length - 1;
while (start < end) {
swap(charArray, start, end);
start += 1;
end -= 1;
}
return charArray.join("");
}
function swap(charArray, start, end) {
// using destructuring assignment to swap the characters
[charArray[start], charArray[end]] = [charArray[end], charArray[start]];
}
1function reverseString(string) {
2 let charArray = string.split("");
3 let start = 0;
4 let end = charArray.length - 1;
5 while (start < end) {
6 swap(charArray, start, end);
7 start += 1;
8 end -= 1;
9 }
10 return charArray.join("");
11}
12
13function swap(charArray, start, end) {
14 // using destructuring assignment to swap the characters
15 [charArray[start], charArray[end]] = [charArray[end], charArray[start]];
16}
Let's assume that there are n
characters in the given string.
Time Complexity: O(n)
. Both pointers traverse the string from opposite ends until they merge. So every character is processed once in this process. Swapping two characters takes constant amount of time. So the overall time complexity is O(n)
.
Space Complexity: O(n)
. We are using a character array to store the characters of the string. So the space complexity is O(n)
. If the input to the function is a character array itself or the language supports string mutability, then the space complexity would be O(1)
, because the algorithm does an in-place reversal of the character array / string.
Note: While recursion will work for this problem, it overcomplicates the problem without added benefit and as such many interviewers will prefer one of the non-recursive approaches above. We have included the recursive solution here for completeness.
In the previous approach, we iterated two pointers toward the middle of the string and used them to swap the characters at the index of each pointer. While this method works well, we want to present a similar approach that uses recursion.
We define a recursive function that receives the character array and pointers for start and end as input. The function swaps the characters at the start and end pointers. Then it calls itself with the start pointer incremented by 1 and the end pointer decremented by 1. This way, the function keeps swapping the characters at the start and end pointers until the start pointer is greater than the end pointer. The function returns when the start pointer is greater than the end pointer. This way, we can reverse the string in place.
In the end, we convert the character array to a string and return it.
char_array
.reverseStringHelper
with char_array
, 0
and char_array.length - 1
as input.Recursive function reverseStringHelper
:
start
is greater than end
, return.start
and end
.reverseStringHelper
with char_array
, start + 1
and end - 1
as input.function reverseString(string) {
let charArray = string.split("");
reverseStringHelper(charArray, 0, charArray.length - 1);
return charArray.join("");
}
function reverseStringHelper(charArray, start, end) {
if (start > end) {
return;
}
swap(charArray, start, end);
reverseStringHelper(charArray, start + 1, end - 1);
}
function swap(charArray, start, end) {
// using destructuring assignment to swap the characters
[charArray[start], charArray[end]] = [charArray[end], charArray[start]];
}
1function reverseString(string) {
2 let charArray = string.split("");
3 reverseStringHelper(charArray, 0, charArray.length - 1);
4 return charArray.join("");
5}
6
7function reverseStringHelper(charArray, start, end) {
8 if (start > end) {
9 return;
10 }
11 swap(charArray, start, end);
12 reverseStringHelper(charArray, start + 1, end - 1);
13}
14
15function swap(charArray, start, end) {
16 // using destructuring assignment to swap the characters
17 [charArray[start], charArray[end]] = [charArray[end], charArray[start]];
18}
Let's assume that there are n
characters in the given string.
Time Complexity: O(n)
. Both pointers traverse the string from opposite ends until they merge. We swap two characters in the main body of recursion, which is a constant time operation. So the overall time complexity is O(n)
.
Space Complexity: O(n)
. We are using a character array to store the characters of the string. On top of that, we are using the call stack to store the function calls. We make n/2
function calls, which is O(n)
. So, the space complexity is O(n)
.
interviewing.io is a mock interview practice platform. We've hosted over 100K mock interviews, conducted by senior engineers from FAANG & other top companies. We've drawn on data from these interviews to bring you the best interview prep resource on the web.
Interview prep and job hunting are chaos and pain. We can help. Really.