Problem overview
The method Reverse receives a string, input, and returns the same characters in the opposite order, without using built-in reversing helpers. For "hello" it returns "olleh", and for an empty string it returns an empty string.
The statement allows O(n²) time and O(n) extra space. That budget is generous on purpose: it lets this lesson use the simplest possible idea, and a later lesson on the same problem reaches O(n).
Approach: put each new character in front
Read the input from left to right and build the result by placing every character at the front of what you have so far. Tracing "hello":
after 'h': "h"
after 'e': "eh"
after 'l': "leh"
after 'l': "lleh"
after 'o': "olleh"
The first character read ends up last, and the last one ends up first, which is exactly a reversal.
The price is in the copying. A C# string can't be changed after it is created, so character + reversedString allocates a new string and copies every character of the old one into it. The copies cost 1, 2, 3, ... up to n - 1 characters, which adds up to about n²/2, so the whole method is O(n²). This is the cost the statement permits. Appending to a StringBuilder, as the next lesson does, avoids it.
Step by step
- Start with an empty result.
reversedStringbegins as"", so an empty input falls straight through to the return. - Loop over the characters.
input.ToCharArray()copies the string into achar[], andforeachhands out onecharat a time ascharacter. Looping overinputdirectly would also work, since a string is a sequence ofcharvalues. - Prepend the character. Assign
character + reversedStringback toreversedString. Because one operand is a string,+joins text instead of adding numbers. - Return the result once the loop has visited every character.
The solution in C#
class Solution {
public string Reverse(string input) {
string reversedString = "";
foreach (char character in input.ToCharArray()) {
reversedString = character + reversedString;
}
return reversedString;
}
}
A few C# details are worth noticing:
char + stringis concatenation. The result of joining acharand astringis astring. The trap is two characters:'a' + 'b'adds their numeric codes and gives theint195. Here one side is always a string, so the order of operands doesn't matter for the type.- The assignment is needed. A string never changes in place, so writing just
character + reversedString;would compute a new string and discard it. foreachvariables are read-only. You can't assign tocharacterinside the loop, which suits this solution.- Characters are UTF-16 code units. Letters such as
éare onechar, but an emoji takes two. Reversing code units would swap the halves of such a pair and corrupt it. The lesson's inputs are plain text, so this doesn't come up.
Complexity
Time: O(n²). The loop runs n times. In iteration k the concatenation copies the k characters built so far plus the new one, so the total number of character copies is roughly 1 + 2 + ... + n, about n²/2. Dropping the constant gives O(n²). The ToCharArray() call adds one O(n) pass, which doesn't change the result.
Space: O(n). The character array holds n characters and the result grows to n. Each intermediate string becomes garbage after the next iteration, so only a few strings of length up to n exist at any moment.
Edge cases and common mistakes
- Empty string. The loop body never runs and the method returns
"". - One character.
"a"comes back unchanged. - Appending instead of prepending.
reversedString + characterrebuilds the original string. - Forgetting to assign back. Without
reversedString =the result stays empty. - Using a different method name. The tests call
Reverse, with a capital R, on astringparameter namedinput.
Testing
"hello"gives"olleh"."a"gives"a".""gives""."ab cd"gives"dc ba"; the space is just another character.