Problem overview
The method Reverse receives a string, input, and returns its characters in reverse order, without built-in reversing helpers. "hello" becomes "olleh", and an empty string stays empty.
This time the statement asks for O(n) time and O(n) extra space. The simple approach of putting each new character in front of the result takes O(n²), so it is too slow here, and the lesson needs a way to build the result without copying it over and over.
Approach: walk backwards and append
If you read the input from the last index down to index 0 and write each character after the previous one, the output is the reversal. For "hello" you visit o, l, l, e, h and append them in that order.
Appending raises the question of what to append to. A C# string is immutable, so result += c creates a brand-new string and copies the old text each time. Over n appends that is the same O(n²) copying as before. StringBuilder solves this: it keeps an internal buffer that has spare room and grows it by a multiple when it fills up, so each Append is amortized O(1). The text becomes a string only once, at the end, with one O(n) copy.
There is a second linear way to do the same job: copy the string into a char[] with ToCharArray(), swap the first and last elements, then the second and second-to-last, and so on toward the middle, and finally build a string with new string(array). It also runs in O(n) time and O(n) space. This lesson uses the builder because appending one character at a time matches the way you would describe the task.
Step by step
- Create a
StringBuildernamedreversedString. The class lives in theSystem.Textnamespace. - Loop backwards. Start
iatinput.Length - 1, the last valid index, continue whilei >= 0, and decrement with--i. For an empty string,Length - 1is-1, so the condition is false at once and the loop never runs. - Append each character.
input[i]is achar, andAppendadds it to the end of the buffer. - Convert and return. The method returns a
string, not aStringBuilder, so finish withreversedString.ToString().
The solution in C#
class Solution {
public string Reverse(string input) {
StringBuilder reversedString = new StringBuilder();
for (int i = input.Length - 1; i >= 0; --i) {
reversedString.Append(input[i]);
}
return reversedString.ToString();
}
}
Details worth knowing:
Lengthis a property. It's writteninput.Lengthwith no parentheses.- Indexing returns a
char.StringBuilderhas anAppend(char)overload, so no conversion is needed. --iandi--behave the same here. The decrement is a standalone statement in the loop header, so the value of the expression is never used.ToString()is required. AStringBuildercan't be returned where astringis expected, and the compiler rejects it.- The namespace.
StringBuilderis defined inSystem.Text, so a program that uses its short name needsusing System.Text;at the top of the file. - UTF-16 code units. Like every
char-based reversal, this one would break an emoji, which occupies twocharvalues. Plain text is unaffected.
Complexity
Time: O(n). The loop runs n times with an amortized O(1) append each. The final ToString() copies n characters once. The total is linear.
Space: O(n). The builder's buffer holds the result, and ToString() creates one more string of the same size. Both are proportional to n. The earlier lesson in this problem has the same space cost but O(n²) time, because it copies a growing string on every step.
Edge cases and common mistakes
- Starting at
input.Length. That index doesn't exist, andinput[input.Length]throws anIndexOutOfRangeException. - Stopping at
i > 0. The first character would be skipped, turning"hello"into"olle". - Empty input. Returns
"", since the builder is never appended to. - Single character. Returns the same character.
- Returning the builder. The code needs
.ToString().
Testing
"hello"gives"olleh"."racecar"gives"racecar"."ab"gives"ba".""gives"".