Reverse String
Problem Description
You are required to write a function that reverses a string, where the input string is given as an array of characters s.
Example
Input: s = ["a","b","c","d","e"]
Output: ["e","d","c","b","a"]
Explanation: The input string "abcde" is reversed to "edcba". The array s is modified in-place to reflect this reversed order.
Input: s = ["x","y","z"]
Output: ["z","y","x"]
Explanation: The input string "xyz" is reversed to "zyx". The array s is modified in-place, changing the order of characters directly in the original array.
Constraints
- The length of the array s is between 1 and 10^5 characters, inclusive.
- Each element s[i] in the array is a printable ASCII character, ensuring that the characters are all valid and recognizable.
Although this problem might seem straightforward, there are different ways to solve it, like using an inbuilt function, forming a new string, or by using two pointers. Each approach has its own benefits and challenges in terms of how fast it works and how much memory it uses.
Naive Approach
Most programming languages provide an inbuilt function or method to reverse strings/arrays. The general approach using such a function involves simply calling it with the string/array as the argument. The function internally efficiently reverses the string/array.
Learn more about inbuilt reverse function
For C++ refer to this Link : https://cplusplus.com/reference/algorithm/reverse/
For Python refer to this Link (In python we use the string slicing) : https://www.w3schools.com/python/python_strings_slicing.asp
For JAVA refer to this Link: https://www.codecademy.com/resources/docs/java/stringbuilder/reverse
For Javascript refer to this Link:
https://www.w3schools.com/jsref/jsref_reverse.asp
Why Avoid using the inbuilt function in an Interview?
While using an inbuilt reverse function is convenient and often the most straightforward approach, it might not be ideal in an interview context for several reasons. Interviewers typically want to see your understanding of basic algorithms and data structures. Implementing the reverse operation manually shows your grasp of fundamental concepts like loops, indexing, and swapping elements.
Though this method is highly efficient and quick to implement, making it an excellent choice for use in Online Assessments (OAs) and coding contests.
Naive Code for All Languages
C++
class Solution {
public:
// Function to reverse the string using the inbuilt reverse function
void reverseString(vector<char>& s) {
// Using the inbuilt reverse function to reverse the entire vector
reverse(s.begin(), s.end());
}
};
Java
class Solution {
// Method to reverse the char array by converting it to a List first
public void reverseString(char[] s) {
// Convert char array to List<Character>
// Since in Java arrays are immutable thats why trasforming
// to List to demonstrate inbuilt reverse
List<Character> charList = new ArrayList<>();
for (char c : s) {
charList.add(c);
}
// Reverse the List in place
Collections.reverse(charList);
// Copy the reversed list back to the array
for (int i = 0; i < s.length; i++) {
s[i] = charList.get(i);
}
}
}
Python
class Solution:
def reverseString(self, s: List[str]) -> None:
# Use the in-place reverse method for lists in Python
s.reverse()
Time Complexity : O(n)
The time complexity of reversing a string using an inbuilt function is typically O(n), where n is the length of the string. It uses the most optimal algorithm to perform the reversal.
Space Complexity : O(1)
The space complexity is usually O(1) since the reversal is done in place, requiring no extra space other than temporary storage for element swapping.
As we discussed earlier, it’s generally recommended to avoid relying on built-in functions during interviews. Let’s now shift our focus toward developing a brute-force approach to solve this problem using our own logic.
Brute Force Approach
Intuition
Our goal is to reverse the given string, meaning the characters should appear in the opposite order. That is, the first character should become the last character, the second character should become second last and so on.
A common example is, if we want to read a word letter by letter we read it from left to right, what if we want to read it in reverse? Yes! we read it from right to left in opposite way, here we don't have to just read but we have to actually reverse the string in that case reading right to left we can note it down in left to right order.
Example if we are given "Hello" we should read it from right to left noting it down from left to right what you will get finally would be "olleH".
So, we would be following the same approach here too, the given array s should be traversed in backward manner, but we make a new array(Lets call it reversed_s) in which we will be filling values in forward manner.
How to fill reversed_s in forward manner while traversing s in opposite manner simultaneously?
If we use a for loop and traverse s in backward order (from len(s) - 1 to 0), the loop will provide elements of s in reverse order. For each element to be placed in forward order, we can use a pointer j starting from 0, which will be used to assign the value of s at the ith position to the jth position of reversed_s.
In code, this will be reversed_s[j] = s[i].
Note: Don’t forget to move the j pointer (i.e., j++) after the value at the jth position is filled.
Once the reversed_s is filled, just copy it back to s, as the function is void type, so we have to do changes in the original array s only, and return it.
Approach
- Create a new array reversed_s that has the same length as the input array s. This array will store the characters in reverse order.
- Use a loop to traverse the original array s from the last character to the first. This loop will help you access each character in reverse order. Also initialize a pointer j = 0, which assign the value starting from the front in reversed_s
- For each character in the original array s, place it in the corresponding position in the new array reversed_s, i.e. reversed_s[j] = s[i], and increment the jth pointer.
- After the loop completes, the new array reversed_s will contain all characters of the original array s in reverse order.
- Use a for loop again and just copy reversed_s back to s i.e. s[i] = reversed_s[i]
- After the loop, just return s.
Dry Run
- Initialize reversed_s and j:
- reversed_s = ["", "", "", "", ""] (an empty array of the same length as s)
- j = 0 (a pointer starting from the beginning of reversed_s)
- Loop through s in reverse order:
- We start from the last character of
sand work our way to the first character.
- We start from the last character of
- Detailed Steps for Each Iteration:
- Iteration 1:
- i = 4 (last index of
s), so s[i] = "e" - reversed_s[j] = s[i], which means reversed_s[0] = "e"
- Increment j by 1: j = 1
- Now, reversed_s = ["e", "", "", "", ""]
- i = 4 (last index of
- Iteration 2:
- i = 3, so s[i] = "d"
- reversed_s[j] = s[i], which means reversed_s[1] = "d"
- Increment j by 1: j = 2
- Now, reversed_s = ["e", "d", "", "", ""]
- Iteration 3:
- i = 2, so s[i] = "c"
- reversed_s[j] = s[i], which means reversed_s[2] = "c"
- Increment j by 1: j = 3
- Now, reversed_s = ["e", "d", "c", "", ""]
- Iteration 4:
- i = 1, so s[i] = "b"
- reversed_s[j] = s[i], which means reversed_s[3] = "b"
- Increment j by 1: j = 4
- Now, reversed_s = ["e", "d", "c", "b", ""]
- Iteration 5:
- i = 0, so s[i] = "a"
- reversed_s[j] = s[i], which means reversed_s[4] = "a"
- Increment j by 1: j = 5
- Now, reversed_s = ["e", "d", "c", "b", "a"]
- Loop Completes:
- At the end of the loop, reversed_s contains all characters of
sin reverse order.
- At the end of the loop, reversed_s contains all characters of
- Copy reversed_s back to s:
- Now that reversed_s contains ["e", "d", "c", "b", "a"], we copy each element back to
s. - Copy Iteration 1:
- s[0] = reversed_s[0], so s[0] = "e"
- Now, s = ["e", "b", "c", "d", "e"]
- Copy Iteration 2:
- s[1] = reversed_s[1], so s[1] = "d"
- Now, s = ["e", "d", "c", "d", "e"]
- Copy Iteration 3:
- s[2] = reversed_s[2], so s[2] = "c"
- Now, s = ["e", "d", "c", "d", "e"]
- Copy Iteration 4:
- s[3] = reversed_s[3], so s[3] = "b"
- Now, s = ["e", "d", "c", "b", "e"]
- Copy Iteration 5:
- s[4] = reversed_s[4], so s[4] = "a"
- Now, s = ["e", "d", "c", "b", "a"]
- Now that reversed_s contains ["e", "d", "c", "b", "a"], we copy each element back to
- Final Output:
- After copying, s is now ["e", "d", "c", "b", "a"], which is the reversed order of the original array.
BruteForce Code for All Languages
C++
class Solution {
public:
// Function to reverse the array of characters
void reverseString(vector<char>& s) {
// Determine the length of the input array
int n = s.size();
// Create a new array to store characters in reverse order
vector<char> reversed_s(n);
// Initialize pointer j to start filling from the beginning of reversed_s
int j = 0;
// Traverse the input array s from the last character to the first
for (int i = n - 1; i >= 0; i--) {
// Place the character from s[i] into reversed_s[j]
reversed_s[j] = s[i];
// Move j to the next position in reversed_s
j++;
}
// Copy the reversed_s array back to s
for (int i = 0; i < n; i++) {
// Assign each character from reversed_s to s
s[i] = reversed_s[i];
}
}
};Java
class Solution {
// Function to reverse the array of characters
public void reverseString(char[] s) {
// Determine the length of the input array
int n = s.length;
// Create a new array to store characters in reverse order
char[] reversed_s = new char[n];
// Initialize pointer j to start filling from the beginning of reversed_s
int j = 0;
// Traverse the input array s from the last character to the first
for (int i = n - 1; i >= 0; i--) {
// Place the character from s[i] into reversed_s[j]
reversed_s[j] = s[i];
// Move j to the next position in reversed_s
j++;
}
// Copy the reversed_s array back to s
for (int i = 0; i < n; i++) {
// Assign each character from reversed_s to s
s[i] = reversed_s[i];
}
}
}Python
class Solution:
# Function to reverse the array of characters
def reverseString(self, s: List[str]) -> None:
# Determine the length of the input array
n = len(s)
# Create a new array to store characters in reverse order
reversed_s = [''] * n
# Initialize pointer j to start filling from the beginning of reversed_s
j = 0
# Traverse the input array s from the last character to the first
for i in range(n - 1, -1, -1):
# Place the character from s[i] into reversed_s[j]
reversed_s[j] = s[i]
# Move j to the next position in reversed_s
j += 1
# Copy the reversed_s array back to s
for i in range(n):
# Assign each character from reversed_s to s
s[i] = reversed_s[i]Javascript
// Function to reverse the array of characters
var reverseString = function(s) {
// Determine the length of the input array
const n = s.length;
// Create a new array to store characters in reverse order
const reversed_s = new Array(n);
// Initialize pointer j to start filling from the beginning of reversed_s
let j = 0;
// Traverse the input array s from the last character to the first
for (let i = n - 1; i >= 0; i--) {
// Place the character from s[i] into reversed_s[j]
reversed_s[j] = s[i];
// Move j to the next position in reversed_s
j++;
}
// Copy the reversed_s array back to s
for (let i = 0; i < n; i++) {
// Assign each character from reversed_s to s
s[i] = reversed_s[i];
}
};Time Complexity : O(n)
In this approach, we create a new array and then fill it with the characters from the original array but in reverse order.
Traversing the Original Array: As we traverse the original array in reverse, we simultaneously fill the new array in the correct order. Let's assume the original array has n characters. The traversal itself requires us to look at each character once, so this step has a time complexity of O(n).
Copying Back to Original Array: After filling the new array, we copy the contents of the new array back into the original array. This operation also involves iterating through each character in the new array and assigning it to the corresponding index in the original array. This step again takes O(n).
Overall Time Complexity: Combining these steps, the total time complexity for the brute force approach is O(n) + O(n) = O(n). This means the time required to reverse the string increases linearly with the length of the string.
Space Complexity : O(n)
Space complexity refers to the amount of extra memory required by the algorithm, not including the input data.
New Array: We are creating a new array to store the reversed characters. Since this new array needs to hold all n characters of the original string, the additional space required is O(n).
The original array is given as input, so we do not count its space in the additional space required by our algorithm.
Overall Space Complexity: Since we are creating a new array of the same size as the original array, the space complexity is O(n).
After discussing the brute force approach, the interviewer might raise concerns about the additional space complexity of O(n) due to the creation of a new array. They may then challenge us to find a more optimized solution that reduces space complexity to O(1), meaning the algorithm should use only a constant amount of extra space.
Optimized Approach
Intuition
To eliminate the need for extra space and the creation of a new array, we can optimize our approach by observing that the value at reverse_s[i] in the brute force method is simply s[n - 1 - i] (where n is the length of array s). This establishes a direct relationship between the indices where values have just interchanged positions. Given this relationship, it becomes evident that creating a new array is unnecessary. Instead, we can efficiently achieve the same result by directly swapping the values at index i and n - 1 - i within the original array. This approach not only preserves the integrity of the original data structure but also reduces the space complexity to O(1), making the solution far more optimal.
Intuition of placing s[n-1-i] at reversed_s[i]?
The first position of the array s is at index 0. The last position of the array s is at index n-1, where n is the length of the array.
- Moving 1 step forward from index 0, the next index is 0 + 1, which is 1. Similarly, moving 2 steps forward, the index will be 0 + 2 which is 2. Generalizing it, moving i steps forward, the index will be 0 + i = i
Thus, the index i can be described as moving i steps forward from the starting index 0.
Similarly,
- Moving 1 step backward from index n-1, the next index is n - 1 - 1, which is n -2. Similarly, moving 2 steps backward, the index will be n - 1 - 2 which is n -3 Generalizing it, moving i steps backward, the index will be n - 1 - i
Thus, the index n-1-i can be described as moving i steps backward from the last index n - 1.
- As we know, the ith step from the front after reversal will become ith position from the back, and as we know the ith step from the back is n - 1 - i. Thus establishing a relationship, s[n-i-1] = reversed_s[i]
Approach
- Use a for loop to iterate from the beginning of the array to the middle. This loop will run from index i = 0 to i < len / 2.
- For each index i, swap the characters at positions i and n - 1 - i (where n is the length of the string) where, len is the length of the string s
- Continue swapping until the loop completes, and the string will be reversed.
Lets Visualize with the below Video
Animation for Understanding Optimal Approach
Why Loop till < len / 2?
Looping from 0 to n/2 in the string reversal process is a crucial requirement that ensures each element is swapped only once, thus achieving the reversal efficiently. Here's why:
- Once you've swapped the first half of the string with the second half, the entire string is reversed.
- Continuing the loop beyond the midpoint (n/2) would result in swapping the already swapped elements back to their original positions, essentially undoing the reversal.
Example
Consider reversing the string s = ["h","e","l","l","o"]:
- Index 0: Swap s[0] with s[4]: Result → ["o","e","l","l","h"]
- Index 1: Swap s[1] with s[3]: Result → ["o","l","l","e","h"]
- Index 2: Middle of the string, no swap needed.
If the loop continued beyond the midpoint:
- Index 3: Swap s[3] with s[1]: This would undo the previous swap, reverting part of the reversal, which is unnecessary.
How to swap two positions?
1. Temporary Variable Method
The temporary variable method involves using a third variable to hold the value temporarily while swapping the elements. This ensures that the value of one element is not lost during the swap.
- Store the value of s[i] in a temporary variable.
- Assign the value of s[n - 1 - i] to s[i].
- Assign the value stored in the temporary variable to s[n - 1 - i].
Example: Let's swap position 0, and n - 1 for s = ["h","e","l","l","o"].
i = 0, n - 1 - i = 4
temp = s[0] → temp = 'h'
s[0] = s[4] → s = ["o","e","l","l","o"]
s[4] = temp → s = ["o","e","l","l","h"]
2. Inbuilt Swap Method
If your programming language provides an inbuilt swap method, you can use it to make the code cleaner and easier to understand. The inbuilt swap function usually takes care of swapping two elements without requiring an additional temporary variable.
Using Inbuilt Swap (Example in C++):
swap(s[i], s[len - 1 - i]);
- swap(a, b): This function swaps the values of a and b. In this code, swap(s[i], s[len - 1 - i]) directly swaps the characters at positions i and len - 1 - i in the array s.
Dry Run
Let’s go through a dry run with the input s = ["a", "b", "c", "d", "e"].
Initial Array: s = ["a", "b", "c", "d", "e"]
Array Length: n= 5
Steps:
- First iteration (i = 0):
We swap the elements at index i = 0 and n - 1 - i = 4.
Swap "a" with "e".
Array after swap: ["e", "b", "c", "d", "a"] - Second iteration (i = 1):
Swap the elements at index i = 1 and n - 1 - i = 3.
Swap "b" with "d".
Array after swap: ["e", "d", "c", "b", "a"] - Third iteration (i = 2):
Now i = 2, which is the middle element.
No swap is needed as the middle element ("c") remains in its position.
Since we’ve completed the loop up to the middle, the array is now fully reversed.
Final Output: ["e", "d", "c", "b", "a"]
Optimal Code for all Languages
C++
class Solution {
public:
// Function to reverse the array of characters
void reverseString(vector<char>& s) {
// Determine the length of the input array
int n = s.size();
// Use a for loop to iterate from the beginning of the array to the middle
for (int i = 0; i < n / 2; i++) {
// Store the character at position i
char temp = s[i];
// Place the character from the end at position i
s[i] = s[n - 1 - i];
// Assign the stored character to the end position
s[n - 1 - i] = temp;
}
}
};Java
class Solution {
// Function to reverse the array of characters
public void reverseString(char[] s) {
// Determine the length of the input array
int n = s.length;
// Use a for loop to iterate from the beginning of the array to the middle
for (int i = 0; i < n / 2; i++) {
// Store the character at position i
char temp = s[i];
// Place the character from the end at position i
s[i] = s[n - 1 - i];
// Assign the stored character to the end position
s[n - 1 - i] = temp;
}
}
}Python
class Solution:
# Function to reverse the array of characters
def reverseString(self, s: List[str]) -> None:
# Determine the length of the input array
n = len(s)
# Use a for loop to iterate from the beginning of the array to the middle
for i in range(n // 2):
# Store the character at position i
temp = s[i]
# Place the character from the end at position i
s[i] = s[n - 1 - i]
# Assign the stored character to the end position
s[n - 1 - i] = tempJavascript
// Function to reverse the array of characters
var reverseString = function(s) {
// Determine the length of the input array
const n = s.length;
// Use a for loop to iterate from the beginning of the array to the middle
for (let i = 0; i < n / 2; i++) {
// Store the character at position i
let temp = s[i];
// Place the character from the end at position i
s[i] = s[n - 1 - i];
// Assign the stored character to the end position
s[n - 1 - i] = temp;
}
};Time Complexity: O(n)
In this optimized approach, we directly swap characters within the original array using the indices i and n - 1 - i. Let’s analyze this step by step:
- We iterate over the array from the first element (i = 0) to the middle of the array (i < n/2). For each element at index i, we swap it with the element at index n - 1 - i.
- Each swap operation takes constant time, O(1).
- Since we need to perform this swap for each element up to the midpoint, we perform approximately n/2 swap operations, but since constants are ignored in Big-O notation, this simplifies to O(n).
- Thus, the overall time complexity of this approach is O(n), meaning the time required to reverse the string increases linearly with the length of the string.
Space Complexity : O(1)
Space complexity refers to the amount of extra memory required by the algorithm, excluding the input data itself.
- Unlike the brute-force method, we do not create any additional arrays. We only use a few extra variables (i, n - 1 - i) to manage the swapping process.
- Since these variables take up a constant amount of space, the space complexity is O(1).
Learning Tip
Having learned the optimal algorithm for reversing an array, you can now apply this algorithm to strings (if the string is mutable). Additionally, you can attempt to solve the following problems that utilize this approach.
Given a string s and an integer k, reverse the first k characters for every 2k characters counting from the start of the string.
Given a string s, reverse only all the vowels in the string and return it.