Remove single character occurrence from String

Question

I want an algorithm to remove all occurrences of a given character from a string in O(n) complexity or lower? (It should be INPLACE editing original string only)

eg.

String="aadecabaaab";

removeCharacter='a'

Output:"decbb"

In javascript this works: "aadecabaaab".split("a").join("") You can employ a similar technique in Java. — Ralph Caraveo, Aug 08 '13 at 20:42
I want an algo. Please don't consider this a problem of Java etc. regarding immutable objects. — pxm, Aug 08 '13 at 20:46
@pxm You'd be constructing a new string anyway as shifting a mutable string would be a worst-case of O(n^2) for the entire algo if my estimation is correct. A StringBuilder is just a specialized string that can be modified, though appending would work in any case in O(n) — nanofarad, Aug 08 '13 at 20:46
Since you *can't mutate a `String` in Java* .. this question is rather silly. The answer is: You can't. If you were talking about arrays ... well, what have you tried? Seems like a `for` loop is `O(n)` to me. — Brian Roach, Aug 08 '13 at 20:48
Sorry for java tag, removed it. Consider it an char array if you want. — pxm, Aug 08 '13 at 20:51
You can consider it anything you'd like. SO isn't a "Give me teh codez" site, especially when it's obviously HS / CS101 homework. — Brian Roach, Aug 08 '13 at 20:52
Ok u're right by the way it was a question in Amazon interview. — pxm, Aug 08 '13 at 21:23

score 3 · Answer 1 · answered Aug 08 '13 at 20:53

3

Enjoy algo:

j = 0
for i in length(a):
  if a[i] != symbol:
    a[j] = a[i]
    j = j + 1

finalize:

length(a) = j

answered Aug 08 '13 at 20:53

rook

5,880
4
39
51

score 1 · Answer 2 · answered Aug 08 '13 at 20:42

1

Strictly speaking, you can't remove anything from a String because the String class is immutable. But you can construct another String that has all characters from the original String except for the "character to remove".

Create a StringBuilder. Loop through all characters in the original String. If the current character is not the character to remove, then append it to the StringBuilder. After the loop ends, convert the StringBuilder to a String.

answered Aug 08 '13 at 20:42

rgettman

176,041
30
275
357

I know it, consider it a problem in C/C++ or any other language. Just need an algo – pxm Aug 08 '13 at 20:44
@pxm You'd be constructing a new string anyway as shifting a mutable string would be a worst-case of `O(n^2)` for the entire operation if my estimation is correct. A StringBuilder is just a specialized string that can be modified, though appending would work in any case in `O(n)`. – nanofarad Aug 08 '13 at 20:45
Sure, it can be generalized to any programming language, but you tagged Java, so I gave a Java algorithm. – rgettman Aug 08 '13 at 20:46
A very sorry for that. Removed it. – pxm Aug 08 '13 at 20:48
This is the algorithm: "Loop through all characters in the original String. If the current character is not the character to remove, then append it to the StringBuilder." – Steve Kuo Aug 08 '13 at 20:50

score 1 · Accepted Answer · answered Aug 08 '13 at 20:50

1

You can't do it in place with a String because it's immutable, but here's an O(n) algorithm to do it in place with a char[]:

char[] chars = "aadecabaaab".toCharArray();
char removeCharacter = 'a';
int next = 0;
for (int cur = 0; cur < chars.length; ++cur) {
    if (chars[cur] != removeCharacter) {
        chars[next++] = chars[cur];
    }
}
// chars[0] through chars[4] will have {d, e, c, b, b} and next will be 5
System.out.println(new String(chars, 0, next));

answered Aug 08 '13 at 20:50

Ted Hopp

232,168
48
399
521

Is this truly O(n) complexity seeing as .toCharArray() also could be O(n) underneath the covers? I am curious. – Ralph Caraveo Aug 08 '13 at 21:26
1

@RalphCaraveo - Two O(n) operations in sequence is still O(n). Presumably, though, providing the input should not be considered part of the run-time complexity. Calling `toCharArray` was just a simple way to get the individual characters out of the string. – Ted Hopp Aug 08 '13 at 21:51

score 0 · Answer 4 · answered Aug 08 '13 at 20:44

0

Yep. In a linear time, iterate over String, check using .charAt() if this is a removeCharacter, don't copy it to new String. If no, copy. That's it.

answered Aug 08 '13 at 20:44

Mysterion

9,050
3
30
52

I don't need new objects. – pxm Aug 08 '13 at 20:50
String is immutable object, you can't change it once it created. – Mysterion Aug 08 '13 at 20:52
This would only work for a mutable object (such as `StringBuilder`). But this is not O(n). Removing a character is an O(n) operation and you are doing it O(n) times. – Ted Hopp Aug 08 '13 at 20:54
Ted, you answer it to me? If yes, my algo is completely O(n), there is no any removing in O(n) complexity – Mysterion Aug 08 '13 at 21:00
When you `removeCharacter`, you need to move the trailing characters one position in the underlying character array (to close up the gap from the removed character). That is an O(n) operation since on average there will be n/2 trailing characters. Since the number of characters to be removed is (also on average) proportional to n, the result is an O(n^2) algorithm. – Ted Hopp Aug 08 '13 at 21:54
@TedHopp I think removeCharacter was a variable in the original question, not a method. – ajb Aug 08 '13 at 23:30
Ah, sorry. I completely misread your answer. On re-reading it, you have an O(n) algorithm. However, it is not an in-place algorithm, which was another one of OP's requirements. – Ted Hopp Aug 08 '13 at 23:40

score 0 · Answer 5 · answered Aug 08 '13 at 20:46

This probably shouldn't have the "java" tag since in Java, a String is immutable and you can't edit it in place. For a more general case, if you have an array of characters (in any programming language) and you want to modify the array "in place" without creating another array, it's easy enough to do with two indexes. One goes through every character in the array, and the other starts at the beginning and is incremented only when you see a character that isn't removeCharacter. Since I assume this is a homework assignment, I'll leave it at that and let you figure out the details.

MasterPlanMan · Answer 6 · 2013-08-08T21:09:36.170

Use a hash table to hold the data you want to remove. log N complexity.

std::string toRemove = "ad";
std::map<char, int> table;
size_t maxR = toRemove.size();  
for (size_t n = 0; n < maxR; ++n)
{
    table[toRemove[n]] = 0;
}

Then parse the whole string and remove when you get a hit (thestring is an array):

size_t counter = 0; 
while(thestring[counter] != 0)
{       
    std::map<char,int>::iterator iter = table.find(thestring[counter]);
    if (iter == table.end()) // we found a valid character!
    {
        ++counter;
    }
    else
    {
        // move the data - dont increment counter
        memcpy(&thestring[counter], &thestring[counter+1], max-counter);
        // dont increment counter
    }
}

EDIT: I hope this is not a technical test or something like that. =S

score 0 · Answer 7 · answered Aug 08 '13 at 20:52

0

import java.util.*;
import java.io.*;

public class removeA{
  public static void main(String[] args){
    String text = "This is a test string! Wow abcdefg.";
    System.out.println(text.replaceAll("a",""));
  }
}

answered Aug 08 '13 at 20:52

SWPhantom

674
5
18

Remove single character occurrence from String

7 Answers7