Reverse String
Reverse String is a easy arrays & hashing problem solved with the two pointer pattern.
The best approach, optimal (two pointers swapping inward), runs in O(n) time and O(1) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (copy backwards) up.
Problem
You are given a word as an array of characters s. Reverse the order of the characters in place: change s itself instead of returning a new array.
Use only O(1) extra memory. Nothing needs to be returned.
Examples
Example 1
- Input
s = ["c", "o", "d", "e", "r"]- Output
["r", "e", "d", "o", "c"]- Why
- The first and last letters swap, then the second and fourth; the middle letter stays.
Example 2
- Input
s = ["Z", "z", "9", "!"]- Output
["!", "9", "z", "Z"]- Why
- Any printable character can appear; with an even length every character moves.
Constraints
1 <= s.length <= 10^5- Each
s[i]is a printable ASCII character. - Modify
sin place using O(1) extra memory.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (2 examples, or your own). Submit also runs 10 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (copy backwards) | O(n) | O(n) |
| Optimal (two pointers swapping inward) | O(n) | O(1) |
1Brute force (copy backwards)
O(n)Two passes over the n characters.O(n)The temporary copy holds all n characters.Build a reversed copy in a second array, then write it back into s. Simple, but it uses O(n) extra memory, which the problem forbids.
- Create an array
copyof the same length. - For every i, set copy[i] = s[n - 1 - i].
- Copy every character of
copyback intos.
class Solution {
public void reverseString(char[] s) {
int n = s.length;
char[] copy = new char[n];
for (int i = 0; i < n; i++) {
copy[i] = s[n - 1 - i];
}
for (int i = 0; i < n; i++) {
s[i] = copy[i];
}
}
}class Solution:
def reverseString(self, s: List[str]) -> None:
n = len(s)
copy = [""] * n
for i in range(n):
copy[i] = s[n - 1 - i]
for i in range(n):
s[i] = copy[i]class Solution {
public:
void reverseString(vector<char>& s) {
int n = s.size();
vector<char> copy(n);
for (int i = 0; i < n; i++) {
copy[i] = s[n - 1 - i];
}
for (int i = 0; i < n; i++) {
s[i] = copy[i];
}
}
};function reverseString(s) {
const n = s.length;
const copy = new Array(n);
for (let i = 0; i < n; i++) {
copy[i] = s[n - 1 - i];
}
for (let i = 0; i < n; i++) {
s[i] = copy[i];
}
}2Optimal (two pointers swapping inward)
O(n)Each character is touched by exactly one swap: n / 2 swaps in total.O(1)Only two indices and one temporary character.Put one pointer at each end. Swap the two characters, then move the pointers toward each other. When they meet or cross, every character has reached its mirrored position.
- Set left = 0 and right = n - 1.
- While left < right: swap s[left] and s[right].
- Increase left and decrease right.
class Solution {
public void reverseString(char[] s) {
int left = 0, right = s.length - 1;
while (left < right) {
char tmp = s[left];
s[left] = s[right];
s[right] = tmp;
left++;
right--;
}
}
}class Solution:
def reverseString(self, s: List[str]) -> None:
left, right = 0, len(s) - 1
while left < right:
s[left], s[right] = s[right], s[left]
left += 1
right -= 1class Solution {
public:
void reverseString(vector<char>& s) {
int left = 0, right = (int)s.size() - 1;
while (left < right) {
swap(s[left], s[right]);
left++;
right--;
}
}
};function reverseString(s) {
let left = 0, right = s.length - 1;
while (left < right) {
const tmp = s[left];
s[left] = s[right];
s[right] = tmp;
left++;
right--;
}
}Edge cases to test
- A single character (nothing changes)
- Two characters (one swap)
- Odd length, where the middle character stays put
- A palindrome like ["a", "b", "a"] (the result equals the input)
Hints
Hint 1
Which character ends up at index 0, and which one at index n - 1?
Hint 2
Swap the two ends, then move both ends one step inward. When do you stop?
FAQ
What is the best time complexity for Reverse String?
Optimal (two pointers swapping inward) runs in O(n) time and O(1) extra space. Each character is touched by exactly one swap: n / 2 swaps in total.
Which pattern does Reverse String use?
It is a arrays & hashing problem that uses the two pointer pattern. Other problems with the same pattern: Two Sum II - Input Array Is Sorted, Valid Triangle Number, Container With Most Water.
Is there a brute force solution for Reverse String?
Yes. Brute force (copy backwards) takes O(n) time and O(n) space. Build a reversed copy in a second array, then write it back into s.
Which edge cases should I test for Reverse String?
A single character (nothing changes); Two characters (one swap); Odd length, where the middle character stays put; A palindrome like ["a", "b", "a"] (the result equals the input).