Problem overview
The function reverse receives a string, input, and returns a new string with the same characters in the opposite order. The statement asks for no built-in helpers that do the reversal for you, so the work is done by hand.
For "hello" the answer is "olleh". The note in the statement allows O(n^2) time and O(n) extra space, which is a generous budget: the simple method below fits it exactly.
Approach: put each new character in front
Start with an empty result and visit the characters of input from left to right. Each time, place the current character in front of everything collected so far. Following "hello":
after 'h': "h"
after 'e': "eh"
after 'l': "leh"
after 'l': "lleh"
after 'o': "olleh"
The first character ends up last, the last character ends up first, and nothing else is needed. No indexes, no swapping.
The price is time. A Kotlin String can't be changed, so putting a character in front builds a brand-new string and copies every character collected so far into it. The first step copies 1 character, the second 2, and so on up to n, which adds up to about n²/2 copies. That is O(n^2), which the statement allows. A faster version, O(n), appends to a StringBuilder from the back; this lesson takes the simple route.
Step by step
- Start with an empty string in
reversedString. It is avar, because every pass of the loop assigns a new string to it. - Loop over the characters. A
for-in loop hands out eachCharofinputin order. The loop variable is namedcharacter. - Prepend. The new value of
reversedStringischaracterfollowed by the old value. Kotlin allows aCharon the left of+when aStringis on the right, and the result is aString. - Return
reversedStringafter the loop has visited every character.
The solution in Kotlin
class Solution {
fun reverse(input: String): String {
var reversedString = ""
for (character in input) {
reversedString = character + reversedString
}
return reversedString
}
}
Kotlin details that matter here:
- The order of the operands.
character + reversedStringworks becauseCharhas aplusfunction that accepts aString. Written the other way,reversedString + character, it would append instead of prepend and return the input unchanged. - Looping over a string. A
Stringcan be used directly infor (character in input). Each element is aChar, a single UTF-16 code unit. - Why
var. Strings are immutable, so the loop doesn't modify one. It makes a new string every time and re-points the variable at it. Withvalthe assignment wouldn't compile. - The return type. The function declares
String, andreversedStringis inferred asStringfrom"", so no conversion is needed.
Complexity
Time: O(n^2). The loop runs n times. On pass k the concatenation creates a string of length k and copies k characters, so the total is 1 + 2 + ... + n, which is about n²/2. For a 100,000-character input that is around five billion character copies, noticeably slow. For the short inputs in the lesson it doesn't matter.
Space: O(n). The result holds n characters. The intermediate strings are discarded as the loop goes, so only a couple of them exist at any moment.
Edge cases and common mistakes
- Empty string. The loop body never runs, and the function returns
"". - One character.
"a"returns"a". - Appending instead of prepending.
reversedString + charactercompiles and runs, but returns the original string. - Palindromes.
"madam"reverses to"madam", so a test can't tell a correct answer from a function that returns its input unchanged. Use a non-palindrome such as"hello"when you check your work. - Emoji and other characters outside the basic range. A
Charis a UTF-16 code unit, and an emoji takes two of them. Reversing code unit by code unit turns the pair around, and the emoji breaks. The lesson's inputs are ordinary text where this doesn't come up.
Testing
"hello"gives"olleh".""gives""."a"gives"a"."ab"gives"ba"."madam racecar madam"gives"madam racecar madam".