Problem overview
The function reverse takes a string, input, and returns a new string with its characters in the opposite order. For "hello" the result is "olleh". The statement asks for O(n) time and O(n) extra space, so the function may visit each character a constant number of times and may use one extra buffer the size of the input.
Approach: read backwards, append forwards
A simple way to reverse is to put each character in front of the result so far. That works, but a Kotlin String is immutable, so every concatenation copies everything built up to that point, and the total work grows as O(n^2). The prepending version of this lesson accepts that cost. Here the budget is O(n), so the copying has to go.
The fix has two parts:
- Read
inputfrom the last index down to 0, so the characters arrive in the order the answer needs them. - Collect them in a
StringBuilder, a buffer that grows in place. Adding one character at its end is amortized constant time, because the builder doubles its capacity when it runs out of room and doesn't copy on every append.
With "hello", the loop reads o, l, l, e, h and appends each one, so the builder ends up holding "olleh". Each of the n characters is read once and appended once, which gives O(n) overall.
Step by step
- Create the builder.
StringBuilder()starts empty. It is declared withval, since the variable always points to the same builder and only the builder's contents change. - Loop over the indexes backwards.
input.length - 1 downTo 0is a range that starts at the last valid index and counts down to 0, including both ends. The loop variable isi. - Append one character.
input[i]reads theCharat positioni, andappendadds it to the end of the builder. - Convert and return. The function must return a
String, and aStringBuilderis a different type.toString()makes the string from the builder's contents.
The solution in Kotlin
class Solution {
fun reverse(input: String): String {
val reversedString = StringBuilder()
for (i in input.length - 1 downTo 0) {
reversedString.append(input[i])
}
return reversedString.toString()
}
}
Kotlin details worth knowing:
downTois an infix function.input.length - 1 downTo 0reads as(input.length - 1) downTo 0, because arithmetic binds tighter than the named infix function. It builds a descending range, both ends included. The shorter0 until nis for counting up and excludes its end, andn - 1 downTo 0is the counting-down counterpart.- Empty input. For
""the range is-1 downTo 0, which contains no values, so the loop body never runs. A range written withdownTonever counts upward, which is what makes this safe. StringBuilderis Java's class. On the JVM, Kotlin usesjava.lang.StringBuilderwithout any import, andappendaccepts aChardirectly.input[i]is aChar. Appending theCharputs a single character in the builder. Appendinginput[i].toString()would give the same result, with an extra temporary string.- Do not return the builder.
return reversedStringis a type error, since the declared return type isString. The calltoString()is required.
Complexity
Time: O(n). The loop runs n times. Each iteration does one index read and one append, both constant time on average. The final toString() copies n characters once. In total, the work is proportional to n.
Space: O(n). The builder holds n characters, and toString() creates a second copy of the same size. Both are linear, so the total stays O(n).
Edge cases and common mistakes
- Starting at
input.length. The valid indexes are 0 tolength - 1.input[input.length]throws aStringIndexOutOfBoundsExceptionon the first pass. - Stopping at 1. A range
input.length - 1 downTo 1skips the first character, so"hello"would give"olle", and thehis lost. - Using
untilwith a descending loop.for (i in input.length - 1 until 0)never runs, becauseuntilonly counts upward. The function would return an empty string. - Empty string. Returns
"", as described above. - Single character. The loop runs once and returns the same character.
- Emoji. A
Charis a UTF-16 code unit, and an emoji uses two. Reading and appending one unit at a time reverses the pair and corrupts the emoji. For such text,StringBuilder.reverse()orString.reversed()handles it correctly, but this lesson's inputs are plain text.
Testing
"hello"gives"olleh".""gives""."a"gives"a"."ab"gives"ba"."abc def"gives"fed cba".