import java.util.HashMap;
import java.util.Map;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
 
public class Main {
 
    public static void main(String[] args) {
        Map<String, String> tokensMap = new HashMap<>();
        tokensMap.put("fizz", "FIZZZZZ");
        tokensMap.put("buzz", "BUZZZZ");
        System.out.println(substituteAllTokens(tokensMap, "hth  trh${fizz} trh thtrht  ${buzz} trhthh trh trh trh"));
    }
 
    private static String substituteAllTokens(Map<String, String> tokensMap, String toInspect) {
        String regex = "\\$\\{([^}]*)\\}";
        Pattern pattern = Pattern.compile(regex);
        Matcher matcher = pattern.matcher(toInspect);
        while (matcher.find()) {
            String token = matcher.group(); // Ex: ${fizz}
            String tokenKey = matcher.group(1); // Ex: fizz
            String replacementValue = null;
 
            if (tokensMap.containsKey(tokenKey))
                replacementValue = tokensMap.get(tokenKey);
            else
                throw new RuntimeException("String contained an unsupported token.");
 
            toInspect=toInspect.replaceFirst(Pattern.quote(token), replacementValue);
            //matcher.reset(toInspect);//REMOVE THIS AND see if it works
 
        }
 
        return toInspect;
    }
}

aW1wb3J0IGphdmEudXRpbC5IYXNoTWFwOwppbXBvcnQgamF2YS51dGlsLk1hcDsKaW1wb3J0IGphdmEudXRpbC5yZWdleC5NYXRjaGVyOwppbXBvcnQgamF2YS51dGlsLnJlZ2V4LlBhdHRlcm47CgpwdWJsaWMgY2xhc3MgTWFpbiB7CgogICAgcHVibGljIHN0YXRpYyB2b2lkIG1haW4oU3RyaW5nW10gYXJncykgewogICAgICAgIE1hcDxTdHJpbmcsIFN0cmluZz4gdG9rZW5zTWFwID0gbmV3IEhhc2hNYXA8PigpOwogICAgICAgIHRva2Vuc01hcC5wdXQoImZpenoiLCAiRklaWlpaWiIpOwogICAgICAgIHRva2Vuc01hcC5wdXQoImJ1enoiLCAiQlVaWlpaIik7CiAgICAgICAgU3lzdGVtLm91dC5wcmludGxuKHN1YnN0aXR1dGVBbGxUb2tlbnModG9rZW5zTWFwLCAiaHRoICB0cmgke2Zpenp9IHRyaCB0aHRyaHQgICR7YnV6en0gdHJodGhoIHRyaCB0cmggdHJoIikpOwogICAgfQoKICAgIHByaXZhdGUgc3RhdGljIFN0cmluZyBzdWJzdGl0dXRlQWxsVG9rZW5zKE1hcDxTdHJpbmcsIFN0cmluZz4gdG9rZW5zTWFwLCBTdHJpbmcgdG9JbnNwZWN0KSB7CiAgICAgICAgU3RyaW5nIHJlZ2V4ID0gIlxcJFxceyhbXn1dKilcXH0iOwogICAgICAgIFBhdHRlcm4gcGF0dGVybiA9IFBhdHRlcm4uY29tcGlsZShyZWdleCk7CiAgICAgICAgTWF0Y2hlciBtYXRjaGVyID0gcGF0dGVybi5tYXRjaGVyKHRvSW5zcGVjdCk7CiAgICAgICAgd2hpbGUgKG1hdGNoZXIuZmluZCgpKSB7CiAgICAgICAgICAgIFN0cmluZyB0b2tlbiA9IG1hdGNoZXIuZ3JvdXAoKTsgLy8gRXg6ICR7Zml6en0KICAgICAgICAgICAgU3RyaW5nIHRva2VuS2V5ID0gbWF0Y2hlci5ncm91cCgxKTsgLy8gRXg6IGZpenoKICAgICAgICAgICAgU3RyaW5nIHJlcGxhY2VtZW50VmFsdWUgPSBudWxsOwoKICAgICAgICAgICAgaWYgKHRva2Vuc01hcC5jb250YWluc0tleSh0b2tlbktleSkpCiAgICAgICAgICAgICAgICByZXBsYWNlbWVudFZhbHVlID0gdG9rZW5zTWFwLmdldCh0b2tlbktleSk7CiAgICAgICAgICAgIGVsc2UKICAgICAgICAgICAgICAgIHRocm93IG5ldyBSdW50aW1lRXhjZXB0aW9uKCJTdHJpbmcgY29udGFpbmVkIGFuIHVuc3VwcG9ydGVkIHRva2VuLiIpOwoKICAgICAgICAgICAgdG9JbnNwZWN0PXRvSW5zcGVjdC5yZXBsYWNlRmlyc3QoUGF0dGVybi5xdW90ZSh0b2tlbiksIHJlcGxhY2VtZW50VmFsdWUpOwogICAgICAgICAgICAvL21hdGNoZXIucmVzZXQodG9JbnNwZWN0KTsvL1JFTU9WRSBUSElTIEFORCBzZWUgaWYgaXQgd29ya3MKICAgICAgICAgICAgCiAgICAgICAgfQoKICAgICAgICByZXR1cm4gdG9JbnNwZWN0OwogICAgfQp9