CODEWITHSUNDEEP
stringalgorithmduplicates
pxm
pxm

Reputation: 1611

Remove single character occurrence from String

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"

Upvotes: 0

Views: 1887

Answers (7)

MasterPlanMan
MasterPlanMan

Reputation: 1032

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

Upvotes: 0

rook
rook

Reputation: 6240

Enjoy algo:

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

finalize:

length(a) = j

Upvotes: 3

SWPhantom
SWPhantom

Reputation: 688

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",""));
  }
}

Upvotes: 0

Ted Hopp
Ted Hopp

Reputation: 234795

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));

Upvotes: 1

ajb
ajb

Reputation: 31689

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.

Upvotes: 0

Mysterion
Mysterion

Reputation: 9320

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.

Upvotes: 0

rgettman
rgettman

Reputation: 178263

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.

Upvotes: 1

Related Questions