Can We Do Better Than Brute Force?

However, it wouldn't really be an interesting algorithms question if there wasn't a better way. Let's see how we can optimize this, or make it run faster. When trying to make something more efficient, it helps to think of things to cut or reduce.

One thing to note is that we're going through the entire string-- do we truly need to iterate through every single letter?

Let's examine a worst case scenario. What if the string is a million characters long? That would be a million operations to work through! Can we improve it?

Yes, With More Pointers!

Well, we're only working with a single pointer right now. The iterator from our loop starts from the back, and appends each character to a new string, one by one. Having gone through The Two Pointer Technique, we may recognize that some dramatic improvements can be had by increasing the number of pointers we use.

By this I mean, we can cut the number of operations in half. How? What if we did some swapping instead? By using a while loop and two pointers-- one on the left and one on the right.

With this in mind-- the big reveal is that, at each iteration, we can swap the letters at the pointer indices. After swapping, we would increment the left pointer while decrementing the right one. That could be hard to visualize, so let's see a basic example listed out.

1jake    // starting string
2
3eakj    // first pass
4^  ^
5
6ekaj    // second pass
7 ^^