OK, so I don't understand why this gave an exception, but it seems that what you need to do is escape the last curly brace. So instead of
myString.replaceAll("\"example\"(.+?)}", "");
you do
myString.replaceAll("\"example\"(.+?)\\}", "");
^^
The first string worked for me in Java 1.7.0_51 and 1.8.0_05, so I'm not sure how this came about... But it works?