Problem overview
The function reverseString takes a string, input, and returns it reversed, without using library helpers. For "hello" the answer is "olleh". The statement allows O(n²) time and O(n) extra space, which is a generous budget: the simplest idea fits inside it.
Approach: put each character in front
Start with an empty result. Walk through the input from left to right, and place every character at the front of the result. After h the result is "h", after e it is "eh", then "leh", "lleh" and finally "olleh". The last character read ends up first, which is exactly a reversal.
This is slower than it looks. A Go string is immutable, so string(character) + reversedString cannot insert in place. It allocates a new string and copies the old content into it. The k-th prepend copies about k bytes, so the total is 1 + 2 + … + n, which is O(n²). That matches the statement's budget. A faster version with O(n) time exists, and it is a separate lesson on this problem.
Tracing the loop on "abc" makes the order concrete:
start: reversedString = ""
character a: reversedString = "a"
character b: reversedString = "ba"
character c: reversedString = "cba"
The new character always goes on the left of what was built before, so earlier characters are pushed to the right. Nothing needs to know the length of the input in advance, and there is no index arithmetic to get wrong, which makes this the easiest correct version to write.
Step by step
- Declare
reversedStringwith:=and an empty string. It accumulates the answer. - Loop over
inputwithrange. The index is not needed, so it is discarded with the blank identifier_, and each element is namedcharacter. - Inside the loop, replace
reversedStringwith the new character followed by the old content. - Return
reversedStringafter the loop.
The solution in Go
func reverseString(input string) string {
reversedString := ""
for _, character := range input {
reversedString = string(character) + reversedString
}
return reversedString
}
Language details worth knowing
range over a string decodes UTF-8 and yields runes. A rune is a Unicode code point and has an integer type, so character is a number, not a string. Go only concatenates strings with +, which is why the loop converts it with string(character). Without the conversion the code does not compile.
Looping over runes rather than bytes keeps non-ASCII text intact. Called on "héllo", where é takes two bytes, the function returns "olléh". The accent stays on the right letter.
The string is rebuilt on every pass, and the old value becomes garbage that Go cleans up. You never modify a string, you only assign a new one to the variable.
One more point about the loop variable: in for _, character := range input, Go gives two values per pass, the byte index and the rune. Because Go rejects unused variables, you must either use the index or write _ in its place, as the solution does.
Complexity
Time is O(n²) in the worst case, from the repeated copying described above. Space is O(n): at any moment the program holds the result so far, plus the temporary new string, both at most n bytes long.
Edge cases and common mistakes
- An empty string returns an empty string, because the loop never runs.
- A single character is returned unchanged.
- Writing
character + reversedStringwithoutstring(...)fails to compile, because a rune and a string can't be added. - Appending instead of prepending (
reversedString + string(character)) just copies the input. - Invalid UTF-8 bytes decode as the replacement character U+FFFD during
range, so such input doesn't come back byte for byte. Normal text is not affected. - Reversing by runes keeps each code point whole, but a visible character built from several code points (a letter plus a combining accent) would still be split.
Testing
"hello"gives"olleh".""gives""."a"gives"a"."ab"gives"ba".