How to avoid String.matches denial of service attack regex

Question

In our application we wish for the user to have the ability to enter a regex to match against data that will be later provided to us.

We then run this through String.matches() This appears to be susceptible to a Denial of service attack.

The advice I have found on avoiding this seems to revolve around being careful on how you craft your regex. As we don't have control over what the user chooses to enter this isn't an option.

What other options are available to me?

This code takes over 7 minutes. Adding 2x's to the string seemed to treble execution time.

    String regex = "(x\\w{1,10})+y";
    boolean matches = "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx".matches(regex);
    System.out.println(matches);