How to replace string only once without regex in Java?

You should use already tested and well documented libraries in favor of writing your own code!

StringUtils.replaceOnce("aba", "a", "")    = "ba"

The StringUtils class is from Apache Commons Lang3 package and can be imported in Maven like this:

<dependency>
    <groupId>org.apache.commons</groupId>
    <artifactId>commons-lang3</artifactId>
    <version>3.8.1</version>
</dependency>

As Laurence suggested, you can use Pattern.quote like this:

newString = string.replaceFirst(Pattern.quote(substring),
                                Matcher.quoteReplacement(replacement));

quote creates a regex that literally matches the substring, and quoteReplacement creates a literal replacement string.

Another approach is simply to compile the substring as a literal regex like this:

newString = Pattern.compile(substring, Pattern.LITERAL).
        matcher(string).replaceFirst(Matcher.quoteReplacement(replacement));

This might be slightly more efficient, but also a bit less clear.

You could also do it manually, since you're only wanting to replace the first occurrence. But regexes are pretty efficient, so don't optimise prematurely!

make sure to also replace \s and $s in the replacement as well. This is probably what you want because you can't have any subgroups with yours ()'s being removed).

newStr = str.replaceFirst(Pattern.quote(target), Matcher.quoteReplacement(replacement));

Solution with Pattern

You could also change the String.replace method that uses the literal interpretation of characters to replace only the first occurrence of the target character sequence:

/**
 * Replaces the first subsequence of the <tt>source</tt> character sequence
 * that matches the literal target sequence with the specified literal
 * replacement sequence.
 * 
 * @param source source sequence on which the replacement is made
 * @param target the sequence of char values to be replaced
 * @param replacement the replacement sequence of char values
 * @return the resulting string
 */
private static String replaceFirst1(CharSequence source, CharSequence target, CharSequence replacement) {
    return Pattern.compile(target.toString(), Pattern.LITERAL).matcher(
        source).replaceFirst(Matcher.quoteReplacement(replacement.toString()));
}

From the documentation of Pattern.LITERAL:

When this flag is specified then the input string that specifies the pattern is treated as a sequence of literal characters. Metacharacters or escape sequences in the input sequence will be given no special meaning.

Solution without Pattern

The other and more efficient way, of course, is to use Alex Martelli's hint to produce the following functionality:

/**
 * Replaces the first subsequence of the <tt>source</tt> string that matches
 * the literal target string with the specified literal replacement string.
 * 
 * @param source source string on which the replacement is made
 * @param target the string to be replaced
 * @param replacement the replacement string
 * @return the resulting string
 */
private static String replaceFirst2(String source, String target, String replacement) {
    int index = source.indexOf(target);
    if (index == -1) {
        return source;
    }

    return source.substring(0, index)
        .concat(replacement)
        .concat(source.substring(index+target.length()));
}

Time measurement

Based on 10 runs, the replaceFirst2 method executes about 5 times faster than the replaceFirst1 method. I have put both of these methods in a loop with 100.000 repeats and got the following results, in milliseconds:

    Method                 Results (in ms)             Average
replaceFirst1: 220 187 249 186 199 211 172 199 281 199 | 210
replaceFirst2:  40  39  58  45  48  40  42  42  43  59 |  45

StringBuilder class in java can be used very easily to do a non-regex based replacement of one string with another.

private static String replace(String in, String ths, String that) {
    
    StringBuilder sb = new StringBuilder(in);

    int idx = sb.indexOf(ths); 
    
    while (idx > -1) {
        sb.replace(idx, idx + ths.length(), that);
        idx = sb.indexOf(ths);
    }
    
    return sb.toString(); 
    
}

Pattern.quote does not seem to work in all cases. Try `Pattern.quote(":-)");