Сгруппируйте три сегмента, которые являются частью перед замененной строкой, замененной строкой и остальными, и соберите префикс, замену и суффикс:
String pattern = String.format("^(.*?%1$s.*?%1$s.*?)(%1$s)(.*)$", "abc");
String result = input.replaceAll(pattern, "$1xyz$3");
Это решение предполагает, что весь вводэто одна строка.Если у вас есть многострочный ввод, вам придется заменить точки, поскольку они не соответствуют разделителям строк.