Wow, & is a good use

Thanks for the pointer (no pun intended)! In hindsight that's a clear optimisation.

I think this is O(n^2) because String.sub creates a new string on each call.

I had the same idea. I avoid creating a new string by keeping track of two pointers, beginning and end.