Problem overview
The function reverse takes a String called input and returns a new String with the same characters in the opposite order. For "hello" the answer is "olleh". The statement asks for O(n) time and O(n) extra space, and rules out built-in reversing helpers, so the lesson swaps characters by hand.
Approach: swap from both ends
Reversing means that the first character trades places with the last, the second with the second to last, and so on until the middle. Two indices do this: left starts at the first position and right at the last. Each round swaps the two characters, then moves both indices one step toward the middle. When left reaches or passes right, every pair has been swapped and the work is done. A middle character in an odd-length string stays where it is, because it is its own mirror.
Rust adds one preliminary problem. A String is stored as UTF-8 bytes, and a single character can take one to four of them, so input[i] is not allowed. The usual fix is to copy the characters into a Vec<char>, where every element is one whole Unicode character and indexing works. That copy is the O(n) extra space the statement allows.
Step by step
- Collect the characters.
input.chars()is an iterator, andcollect()builds a collection from it. It needs to know which collection, and the annotationVec<char>oncharstells it. - Store the length in
n. It is the number of characters, not bytes, because it comes from the vector. - Clone the vector into
result, which is declaredmut. The swaps change this copy and leavecharsas it was. - Set up the pointers as a tuple:
leftat0usizeandrightatn.saturating_sub(1), the last index. Plainn - 1breaks for an empty string, as the edge cases below show;saturating_substops at 0 instead. - Loop while
left < right. When the pointers meet or cross, nothing is left to swap. - Swap.
result.swap(left, right)exchanges the two elements without a temporary variable. - Move the pointers with
left += 1andright -= 1. The subtraction is safe: the loop only runs whenleft < right, sorightis at least 1. - Build the answer.
result.into_iter().collect()turns the vector back into aString. Nothing tellscollectthe target type here except the function's return type, and that is enough. The line has no semicolon, so it is the value the function returns.
The solution in Rust
impl Solution {
fn reverse(input: String) -> String {
let chars: Vec<char> = input.chars().collect();
let n = chars.len();
let mut result = chars.clone();
let (mut left, mut right) = (0usize, n.saturating_sub(1));
while left < right {
result.swap(left, right);
left += 1;
right -= 1;
}
result.into_iter().collect()
}
}
Rust details worth knowing:
collect()is generic. The same method can build aVec, aString, aHashMapand more. The compiler picks from the type it expects, which comes from an annotation or from the return type. With neither, it reports that it can't infer the type.into_iter()consumes the vector. After the call,resultcan't be used. That is fine here because it is the last use, and no elements are copied.- Characters are not bytes.
"héllo".len()is 6, sinceétakes two bytes, but"héllo".chars().count()is 5. Reversing aVec<char>keepséin one piece, and"héllo wörld"becomes"dlröw olléh". - A
charis a Unicode scalar value, not always what a reader sees as one letter. A letter written asefollowed by a combining accent is twochars, and reversing puts the accent before thee. For the lesson's plain text this doesn't matter. - Tuple destructuring.
let (mut left, mut right) = (...)declares two variables at once, and each one gets its ownmut.
Complexity
Time: O(n). Collecting the characters, cloning, the swap loop (about n/2 rounds) and collecting the result each touch every character a constant number of times.
Space: O(n). The code holds chars, its clone result and the final string, which is three copies of size n, still linear. Declaring chars as mut and swapping it directly would avoid the clone and keep a single vector, but the lesson's version is easier to follow because the original stays untouched.
Edge cases and common mistakes
- Empty string. There is nothing to swap. With
n.saturating_sub(1)the right pointer is 0, the loop condition0 < 0is false, and the result is an empty string. With plainn - 1and optimizations on, 0 minus 1 wraps to the largestusize; the loop starts andswappanics with "index out of bounds: the len is 0". In a debug build the subtraction itself panics. - One character.
leftandrightare both 0, the loop doesn't run, and the string comes back unchanged. - Even and odd lengths.
"abcd"swaps two pairs and gives"dcba". In an odd-length string the loop stops with both pointers on the middle character, which stays in place. - Using
<=in the loop condition. When both pointers meet on the middle, the extra round would swap a character with itself and then moverightbelowleft. Forleft = right = 0,right -= 1underflows. Keep the strict<. - Trying to index the string.
input[0]doesn't compile, and slicing with byte ranges can panic in the middle of a multi-byte character. Work on theVec<char>instead.
Testing
"hello"gives"olleh"."abcd"gives"dcba"."a"gives"a".""gives""."héllo wörld"gives"dlröw olléh".
