Removing a character from a string efficiently

Question

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? 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;
}

No, this is definitely *not* O(n). Think about what `newstr = newstr + str.charAt(i)` needs to do. Imagine all n characters aren't the one you're looking for. (And yes, StringBuilder is what you're looking for.) See http://yoda.arachsys.com/java/stringbuffer.html - written ages ago, but just replace `StringBuffer` with `StringBuilder` everywhere. — Jon Skeet, Feb 28 '14 at 08:07
I should have mentioned in the question to try and not use replaceAll as part of the challenge — Liondancer, Feb 28 '14 at 08:12
Have you seen [this question?](http://stackoverflow.com/questions/8894258/fastest-way-to-iterate-over-all-the-chars-in-a-string) — makata, Feb 28 '14 at 08:18

Daniel · Accepted Answer · 2014-02-28T08:22:34.057

3

Strings are immutable in Java, so your answer actually results in len number of strings being created. Which means they are copied len times, so you have O(N*N) code here. StringBuilder is definitely a better approach.

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

A simpler approach would be to use the built in function:

public static String takeOut(String str, char c) {
    return str.replace(String.valueOf(c), "");
}

edited Feb 28 '14 at 08:22

answered Feb 28 '14 at 08:10

Daniel

4,481
14
34

I think you need to fix `StringBuilder newstr = new StringBuilder();` – Liondancer Feb 28 '14 at 08:21
1

Yes I do @Liondancer. That's what I get for staying up late and answering stackoverflow questions ;-) – Daniel Feb 28 '14 at 08:23

score 2 · Answer 2 · answered Feb 28 '14 at 08:07

2

StringBuilder would definitely prevent your code from creating new strings with every iteration. Additionally, is the character to be removed contained only once in the string? Then you could break the for loop after the first match. Also, locally store the result of String#charAt to not call the method twice.

answered Feb 28 '14 at 08:07

Smutje

17,733
4
24
41

multiple times within the string – Liondancer Feb 28 '14 at 08:08

score 2 · Answer 3 · edited Feb 28 '14 at 08:28

2

Have you tried

str.replaceAll(c,"");

? Maybe the Java-Runtime kows the fastest way of replacing (deleting)...

edited Feb 28 '14 at 08:28

user987339

10,519
8
40
45

answered Feb 28 '14 at 08:10

user3363881

101
1
5

2

Don't ask a question.. answer it. (find out the stats ur self) – Hungry Blue Dev Feb 28 '14 at 08:10
It will not be efficient at all – Kick Feb 28 '14 at 08:12

Kick · Answer 4 · 2014-02-28T08:13:39.827

1

My suggestion to replace any char more efficiently would be:

1) Convert the String to a char[] array.

2) Run through the array, testing each character one by one and replacing it if needed and append in StringBuilder

I think this is probably the fastest performance you will get in pure Java.

edited Feb 28 '14 at 08:13

answered Feb 28 '14 at 08:07

Kick

4,823
3
22
29

Removing a character from a string efficiently

4 Answers4