How to efficiently remove all instances of a String from another String?

The problem I am solving is replacing all Strings from another String.

I solved this problem fairly easily on codingbat.com by using String.replaceAll, and doing it until the first String no longer contains the other String.

However, I dislike this method as it is very slow. I have tried searching this website for more efficient methods, and came across these questions:

Fastest way to perform a lot of strings replace in Java

String.replaceAll is considerably slower than doing the job yourself

They solved the problem by using StringUtils and Patterns. I still think these methods are too slow!

When I code problems like these, I like to get my runtime under two seconds with Java. I'm testing this with a String of 1,000,000 characters. String.replaceAll went well over two seconds, and so did the other two methods.

Does anyone have a fast solution for this problem? Thanks!