I think it is feasible to shrink time to ~ aN +

*O*(N log N). How might we go about doing this? How do we get a logarithmic factor in our order? How can this help us speed up our algorithm?

This post points out a pitfall in computing the algorithm efficiency. The questions above and this problem are related. How can we minimize the effects of substring()?