Increase performance of removing character from String

I wrote this function as part of interview practice. This method removes a character from a given string.

I was wondering how I could make this code more efficient when it comes to runtime/space. I think my code is O(n) and I'm not sure if I can increase the efficiency. However, perhaps using things such as StringBuffer or StringBuilder would increase it a bit? I'm not sure as I'm still a bit new to Java.

public static String takeOut(String str, char c) {
    int len = str.length();
    String newstr = "";
    for (int i = 0; i < len; i++) {
        if (str.charAt(i) != c) {
            newstr = newstr + str.charAt(i);
        }
    }
    return newstr;
}

Learn from existing implementations, they usually have solutions to corner cases, common pitfalls and performance bottlenecks. For example, Apache Commons Lang StringUtils also has a remove function. It's implementation is quite simple and similar to yours:

public static String remove(final String str, final char remove) {
    if (isEmpty(str) || str.indexOf(remove) == INDEX_NOT_FOUND) {
        return str;
    }
    final char[] chars = str.toCharArray();
    int pos = 0;
    for (int i = 0; i < chars.length; i++) {
        if (chars[i] != remove) {
            chars[pos++] = chars[i];
        }
    }
    return new String(chars, 0, pos);
}

Anyway, there are some differences:

-
It uses char array. Strings are immutable, the following concatenation creates a new String object:

newstr = newstr + str.charAt(i);

I guess it's slower than changing a value in an array.


Using the string concatenation operator
repeatedly to concatenate n strings requires time quadratic in n.

Source: Effective Java, 2nd edition, Item 51: Beware the performance of string concatenation

-
At the first line it checks whether the String contains the removed character at all. If it doesn't contain it remove saves the creation the char array. It might help but it depends on your input.

-
The code in the question calls String.charAt() in the comparison which checks the given index:

public char charAt(int index) {
    if ((index = value.length)) {
        throw new StringIndexOutOfBoundsException(index);
    }
    return value[index];
}

The StringUtils implementation skips this test since it knows that the index is valid.

(See also: Effective Java, 2nd edition, Item 47: Know and use the libraries)

StackExchange Code Review Q#43032, answer score: 13