Rating:

Brute force, make sure to reverse the replacement order.
My script solved it in 6 minutes using 8GiB of memory.