Start learning free

LESSON 225 OF 347 · TWO POINTERS

Reverse a String in C#: Two Pointers on a char Array

Practice O(n) Read the full explanation

Given a string, write a function that reverses that string without using built-in functions or libraries.

Example:

Input:  "hello"

Output: "olleh"

Note:

Your algorithm should run in O(n) time and use O(n) extra space.


STEP 1 OF 9
    Ctrl + Enter to check

    C# · TWO POINTERS

    Reverse String in C#, explained

    Problem overview

    Reverse takes a string input and returns a new string with the characters in the opposite order: "hello" becomes "olleh". The statement asks for O(n) time and O(n) extra space, and tells you to do the reversal yourself rather than call a library method that does it.

    Approach

    The natural way to reverse something in place is to swap the first element with the last, the second with the second-to-last, and so on until you reach the middle. In C# that can't be done on the string itself, because strings are immutable. Once created, a string never changes. This line doesn't compile:

    string s = "hello";
s[0] = 'j';   // error CS0200: the indexer is read only

    The way around it is to copy the characters into a char[], which can be modified, reverse the array in place, and build a new string from the result. The copy is where the O(n) extra space in the statement comes from. The swaps then take O(n) time.

    Two pointers do the swapping. left starts at index 0 and right at the last index. While left < right, swap the two characters and move both pointers inward. When the pointers meet or cross, every pair has been swapped. For an odd length the middle character stays where it is, and that's correct, because it is its own mirror.

    For "hello" the array starts as h e l l o. The first swap exchanges h and o, and the second exchanges e and l. Then left and right both point at the middle l, the condition fails, and the array reads o l l e h.

    Step by step

    1. Copy the characters. input.ToCharArray() returns a new array, so changing it leaves input untouched.
    2. Create left at 0.
    3. Create right at charArray.Length - 1, the last index.
    4. Write the loop while (left < right). Nothing is left to swap once the pointers meet or cross.
    5. Call a helper, Swap(charArray, left, right), inside the loop. Writing the call first, and the helper afterwards, keeps each piece small.
    6. Declare the helper Swap with parameters char[] arr, int i and int j. It returns void: arrays are reference types, so the caller sees the change.
    7. Swap through a temporary. Save arr[i] in c, copy arr[j] into arr[i], and put c into arr[j].
    8. Move the pointers with left++ and right-- after the swap.
    9. Build the result with new string(charArray) and return it.

    The solution in C#

    class Solution {
    public void Swap(char[] arr, int i, int j) {
        char c = arr[i];
        arr[i] = arr[j];
        arr[j] = c;
    }
    public string Reverse(string input) {
        char[] charArray = input.ToCharArray();
        int left = 0;
        int right = charArray.Length - 1;
        while (left < right) {
            Swap(charArray, left, right);
            left++;
            right--;
        }
        return new string(charArray);
    }
}

    C# details:

    • Why the temporary is needed. Writing arr[i] = arr[j] first would overwrite the original arr[i] before it was saved, and both cells would end up holding the same character.
    • Arrays are passed by reference. Swap receives a reference to the same array that Reverse holds, so its changes are visible afterwards. Without that, the helper would have to return something.
    • new string(char[]) is a constructor that copies the characters into a fresh immutable string. The original input is never modified, so the caller's string is safe.
    • Library alternatives. .NET offers Array.Reverse and a LINQ Reverse that do this in one call. The lesson writes the swaps by hand to practice the pointer technique, and because the statement asks for it.
    • A shorter swap. Modern C# can swap two values with a tuple assignment, (arr[i], arr[j]) = (arr[j], arr[i]);, which does the same job as the temporary variable. The lesson uses the temporary because it shows exactly what happens to each value.
    • The original string survives. After char[] a = s.ToCharArray(); a[0] = 'j'; with s = "hello", the array spells jello while s still holds hello. This independence is the reason copying to an array is safe.
    • Length is a property on both strings and arrays, without parentheses.

    Complexity

    Time: O(n). Copying the characters, the n/2 swaps and building the new string each cost at most a linear amount.

    Space: O(n). The char[] holds n characters, and the returned string is another n. A fixed number of integers and one temporary character are also used.

    Edge cases and common mistakes

    • The empty string. The array has length 0, so right is -1, the loop never runs and the result is an empty string.
    • One character. left equals right, nothing is swapped, and the same character comes back.
    • Trying to assign to the string. Code like input[left] = input[right] doesn't compile, because string indexers are read only. Work on the array.
    • Looping with left <= right. It is harmless, since swapping a cell with itself changes nothing, but < is enough.
    • Returning charArray.ToString(). On an array it gives the type name, System.Char[], not the characters. Use new string(charArray).
    • Forgetting that the loop must move both pointers. If either stays, the same pair is swapped back and forth until the loop is stopped by something else.

    Testing

    • "hello" gives "olleh".
    • "ab" gives "ba".
    • "a" gives "a", and "" gives "".
    • "abcba" gives "abcba", since a palindrome reverses to itself.
    Keep going with C#About 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free