Problem overview
The method reverse receives a string input and returns a new string with the same characters in the opposite order. The example is "hello", which becomes "olleh". The task asks for no built-in reversing helpers, and the lesson allows O(n) time and O(n) extra space.
Approach: swap from both ends
A Scala String is immutable: no operation changes it in place. To reverse it with swaps, first copy its characters into an array, which is mutable. The copy is where the O(n) extra space comes from.
Then use two pointers. left starts at the first position and right at the last. Swap the two characters, move the pointers one step towards each other, and repeat while left < right. When the pointers meet or cross, every character is in its mirrored place. If the length is odd, the middle character stays where it is, and it is correct there. Finally, turn the array back into a string.
For "hello" the array is h e l l o. The first swap exchanges positions 0 and 4 and gives o e l l h. The second exchanges positions 1 and 3 and gives o l l e h. Then left is 2 and right is 2, the loop stops, and the array reads o l l e h, the word "olleh".
Step by step
- Copy the characters.
val charArray = input.toCharArraycreates anArray[Char].valonly stops the variable from being reassigned; the elements of the array can still change. - Create
leftas avarequal to 0. - Create
rightas avarequal tocharArray.length - 1. - Write the loop
while (left < right). Once the pointers meet or cross, nothing is left to swap. - Swap inside the loop with
swap(charArray, left, right). The helper is written next. - Declare the helper
def swap(arr: Array[Char], i: Int, j: Int): Unitabovereverse. It returnsUnit, meaning no useful value, because the array is shared with the caller, so the caller sees the change. - Implement the swap with a temporary. Save
arr(i)inval c, copyarr(j)intoarr(i), then putcintoarr(j). Without the temporary, the first assignment would overwrite a value before it was saved. - Move the pointers after the swap:
left += 1andright -= 1. - Build the result with
new String(charArray), which copies the characters into a new string.
The solution in Scala
class Solution {
def swap(arr: Array[Char], i: Int, j: Int): Unit = {
val c = arr(i)
arr(i) = arr(j)
arr(j) = c
}
def reverse(input: String): String = {
val charArray = input.toCharArray
var left = 0
var right = charArray.length - 1
while (left < right) {
swap(charArray, left, right)
left += 1
right -= 1
}
return new String(charArray)
}
}
The Scala details worth a closer look:
- Immutable strings. Methods on a
Stringnever modify it, which is why the array is needed.inputitself is left unchanged byreverse. - Arrays are passed by reference.
swapreceives the same array object thatreverseholds, so writingarr(i) = arr(j)inside the helper changes the caller's array. The syntaxarr(i) = xis how Scala assigns to an array element. Unitis Scala's "no meaningful value" type. The last line ofswapis an assignment, whose value is(), the single value of typeUnit.new String(charArray)calls the JavaStringconstructor. Scala runs on the JVM and can use Java's classes directly.return. The lesson ends withreturn new String(charArray). The expression alone as the last line would return the same value.
Why not a built-in
Scala strings already have a reverse method, and it would solve the task in one line. The lesson asks you to do the work yourself, because the swap-and-move pattern shows up again in many two-pointer problems: reversing an array in place, partitioning, or checking a palindrome. Learning it on a string, with the extra step of copying into an array, makes the later problems easier to read.
Watching the pointers move
Printing the array after each swap shows the loop at work on "hello":
o e l l h left=1 right=3
o l l e h left=2 right=2The loop ends after two swaps. The pointers meet on the middle letter, l, which doesn't move. A string of n characters always needs n / 2 swaps, rounded down.
Complexity
Time: O(n). Copying the string is O(n). The loop does at most n / 2 swaps, each constant-time, and building the result is another O(n) copy.
Space: O(n). The character array and the new string each hold n characters.
Edge cases and common mistakes
- Empty string.
rightstarts at-1, the loop never runs, and the method returns an empty string. - One character. Both pointers are 0, no swap happens, and
"a"stays"a". - Two characters.
"ab"needs one swap and becomes"ba". - Running the loop too long. With
left <= rightnothing breaks, since the last swap exchanges a character with itself. With a loop that runs for allnpositions, each pair is swapped twice and the string comes back unchanged. - Swapping without a temporary. Writing
arr(i) = arr(j)followed byarr(j) = arr(i)leaves both positions with the same character. - Characters outside the basic plane. A
Charis one 16-bit unit of UTF-16. Emoji and some other symbols take two units, a surrogate pair. Reversing unit by unit puts the pair in the wrong order. For"a😀b"the string has length 4, and the result is not the string"b😀a". The lesson's tests use ordinary text, where oneCharis one character.
Testing
"hello"gives"olleh".""gives""."a"gives"a"."ab"gives"ba".
