Problem overview
The function reverseString takes a string, input, and returns it reversed. For "hello" the answer is "olleh". This time the statement asks for O(n) time and O(n) extra space, so the repeated copying of the earlier approach is not allowed.
Approach: read backwards, write forwards
The slower version prepends each character to a growing string. In Go every such step allocates a new string and copies the old one, so the total work grows as O(n²). To reach O(n), two things change.
- Instead of inserting at the front, read the input from the last index down to 0 and append each element to the result. The order of the output is then already reversed.
- Instead of concatenating immutable strings, collect the output in a
strings.Builder, which keeps a growable buffer. Appending to it is amortizedO(1)per byte, because the buffer grows geometrically and each byte is copied only a few times over the whole run.
The final String() call hands back the accumulated text without copying it again.
Step by step
- Declare
reversedStringwithvaras astrings.Builder. Its zero value is ready to use, so no constructor call is needed. - Loop with an index
ithat starts atlen(input) - 1, continues whilei >= 0, and decrements each pass. That visits the last byte first. - In the loop body, append
input[i]withWriteByte. - After the loop, return
reversedString.String().
The solution in Go
func reverseString(input string) string {
var reversedString strings.Builder
for i := len(input) - 1; i >= 0; i-- {
reversedString.WriteByte(input[i])
}
return reversedString.String()
}
Language details worth knowing
input[i] is a byte, and WriteByte takes a byte, so the types match with no conversion. WriteByte also returns an error value, which is always nil for a builder. Ignoring it is normal here and compiles without complaint.
The function needs the strings package imported. A builder must not be copied after you first use it; since the variable lives and dies inside this function, that never comes up.
The loop counts down, so i-- is the post statement, and the condition is i >= 0. Go's int is signed, so it can go below zero and stop the loop. This would be a bug with an unsigned index type, which would wrap around instead of becoming negative.
Complexity
Time is O(n): one pass over n bytes, each appended in amortized constant time. Space is O(n) for the builder's buffer, which ends up holding a string as long as the input.
Edge cases and common mistakes
- An empty string:
len(input) - 1is-1, the condition fails at once, and the function returns"". - Starting at
len(input)instead oflen(input) - 1reads one past the end and panics. - Stopping at
i > 0would drop the first character of the input from the result. - Reversing bytes is correct for ASCII, but it scrambles any character that uses more than one byte. Reversing
"héllo"this way produces bytes that are not valid UTF-8 and prints as garbage, because the two bytes oféswap places. If the input may contain such characters, convert it to a[]runeand reverse that instead, or loop withrangeas in the slower version. - Using
+=on a string inside this loop would compile and give the right answer, but it brings back theO(n²)copying.
Testing
"hello"gives"olleh".""gives""."a"gives"a"."ab"gives"ba".