LeetCode with C# - Reverse A String

Welcome to my series on LeetCode and solving problems with C#. The goal of this series is to help those who are trying to solve LeetCode problems without directly giving them a copy paste answer.

If you like this article, consider following me over at Medium. The article is available on a paid plan there, but gets released earlier than on dev.to.

You can check that out here: https://coryharkins.medium.com/leetcode-with-c-reverse-a-string-8ebb2f54f88a

To help you direct your brain on how to think about the given problem.

With that let’s get into it. Today’s problem is Reversing a string.
If you just want the solution and skip all the fun, just scroll down to the bottom.

Problem

Write a function that reverses a string. The input string is given as an array of characters char[].

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

You may assume all the characters consist of printable ascii characters.

What does this mean?

We are given an array of characters called s. It is of type char array. We need to reverse this array without allocating additional arrays to hold the data. We need to preform operations on this array and this array alone. The big O notation says that we should solve this with a constant linear time complexity.

If you’d like additional resources on how to solve this problem you can look here.

Linq Solution

public class Solution {
    public void ReverseString(char[] s) {
        Array.Reverse( s );
    }
}

Thoughts on the Linq Solution

Linq provided a very simple and readable way to solve this. You can simply call the Reverse method on your array. Under the hood this is doing something interesting though. From my research the Linq version is allocating a new array and iterating over the source and returning the new array. So this method is cheating; but LeetCode accepts it.

Iterative Solution (Two Pointer Technique)

public void ReverseString(char[] s) 
    {
       int b = 0;
       int e = s.Length - 1;
       char t;
       while (b <= e)
       {
         t = s[b];
         s[b] = s[e];
         s[e] = t;
         b++;
         e--;
       }        
    }

Thoughts on the Two Pointer Technique

The basics of what is going on here is that we have two pointers in the array. One at the beginning (b = 0) and one at the end (e = s.Length -1). We then loop through the array while our starting pointer does not equal our ending pointer.
During this loop we set a variable for our current looking at location to the start of the array (t = s[b];). We then set the first element in the array = to the last, the last equal to the first. Increment our starting index. Decrement our ending index. Then swap it all again until we meet in the middle and break the while loop.

Why does one solution matter over the other?

In short performance. As you can see here in both solutions the Linq solve and the two pointer technique allocate the same amount of memory but the two pointer technique is 60ms faster.

60ms isn’t much to really worry about in an application where timing is not critical.
Here over a longer set of data you can see the performance gains are different as well. Using 60 characters in an array we get the following results in processing time, roughly:
Linq: 420ms.
Two Pointer: 308ms.

Comments

[Mark Davies]

When reversing a string manually I've always gone with a for loop:

var reversed = new char[a.Length]
for(int i = a.Length - 1, j = 0; i >= 0 ; i --, j++){
    reversed[j] = a[i];
}

return reversed;

Not sure if this is faster but it's a lot easier to read in my opinion 😄

[Cory Harkins]

That is much much easier on the eyes! I'm bookmarking this solution.

[Jason]

Just wondering, how do you measure performance? Do you use the stopwatch class?

[Cory Harkins]

I have seen the stopwatch class being used a lot in my research on solving these problems.

Solving this one through LeetCode.com they provide a timing analysis on their site. For this one, I just used the provided stats from LeetCode.

[Félix Pelletier]

Maybe with BenchmarkDotNet, considering its fair popularity and its easiness for setup

[Mark Davies]

Forbidden? AM I gonna get arrested 👀

[Cory Harkins]

In the leet code submission, you'd fail as they don't want you to allocate additional memory to accomplish the task.