Problem overview
The method reverse receives a String named input and returns its characters in the opposite order. For "hello" the answer is "olleh". The task is to write the reversal yourself instead of calling a built-in one.
This version must run in O(n) time and use O(n) extra space, where n is the length of the string.
Approach: read backwards, append to a builder
The simplest reversal builds a result string and puts each new character at its front. That works, but a Scala String can't be modified, so every join creates a new string and copies the old text. The total work is quadratic in the length.
The linear version changes two things:
- It reads the input from the last index down to 0, so the characters arrive already in reverse order and only need to be added at the end.
- It collects them in a
StringBuilder, which holds a growing buffer and appends in place. An append is amortized constant time: when the buffer is full, it is enlarged by a factor, so the copying cost averages out over many appends.
Each of the n characters is read once and appended once, so the time is O(n). The builder holds n characters, so the extra space is O(n).
For "hello", the indices visited are 4, 3, 2, 1, 0, which read 'o', 'l', 'l', 'e', 'h'. Appended in that order, they spell "olleh".
Step by step
- Create the builder with
new StringBuilder()and store it in aval. The variable never needs to point elsewhere, because the builder itself is what changes. - Loop over the indices backwards. The range
input.length - 1 to 0 by -1starts at the last index and counts down to 0. Both ends are included, andby -1sets the step. - Append the character at index
i, read withinput(i). - Convert the builder to a string with
toString()and return that. The method's return type isString, and aStringBuilderis a different type.
The solution in Scala
class Solution {
def reverse(input: String): String = {
val reversedString = new StringBuilder()
for (i <- input.length - 1 to 0 by -1) {
reversedString.append(input(i))
}
return reversedString.toString()
}
}
The Scala details worth knowing:
- Counting down.
a to bcounts up and is empty ifais bigger thanb. To go down you must add a negative step:5 to 0 by -1is 5, 4, 3, 2, 1, 0. Withoutby -1, the loop body would never run. - Empty input. For
""the range is-1 to 0 by -1, which is empty, so the loop does nothing and the method returns"". No special case is needed. - A
valthat changes. Avalfixes which object the name refers to, not the object's contents.appendmodifies the builder behind the name, sovalis fine here. appendaccepts many types. Given aChar, it adds that character; given aStringor anInt, it adds their text. Here it receives aCharfrominput(i).- Parentheses on
toString(). CallingtoStringwith or without them both work in Scala 3 for this Java method.
Complexity
Time: O(n). The loop runs n times and each pass does a constant amount of amortized work: one read and one append. The final toString() copies the buffer once, which is another O(n).
Space: O(n). The builder stores all n characters, and the returned string is a copy of them. The input is not modified.
Edge cases and common mistakes
- Empty string. Returns
"", as explained above. - One character.
"a"gives"a": the range0 to 0 by -1has a single index. - Starting at
input.length. The last valid index islength - 1. Starting atinput.lengthreads past the end and throws aStringIndexOutOfBoundsException. - Stopping at 1. Using
1 by -1as the bound, oruntil 0, skips index 0 and drops the first character from the result. - Forgetting
by -1.input.length - 1 to 0is an empty range for any non-empty input, so the method returns an empty string. - Returning the builder. The method promises a
String; withouttoString()the code does not compile.
Testing
"hello"gives"olleh"."a"gives"a".""gives""."ab cd"gives"dc ba".
