Fastest way to find duplicates in a string without using any additional memory in java?

Question

What is the fastest way to remove duplicate character in a string without using an extra memory in Java?

Answer 1

Use indexOf and delete methods in StringBuilder.

Answer 2

Since a string is immutable you're not going to be able to alter it. Hence, the new version of the string without the duplicate character will consume memory. If you give more details behind the purpose and rationale of your request someone might be able to offer a better approach.

Answer 3

String is immutable, so the reality of it is that you will need to allocate additional memory.

Since you say fastest, I assume you won't consider a 2 pass algorithm. You can go with StringBuilder but that will allocate your original string length + 16, and, when you call getString() you will again be allocating memory in String constructor.

If you don't mind having a 2 pass algorithm, you are looking at 2 allocation of a char[] (of final length of cleaned up string). Use a StringBuilder and you are looking at 2*len + 16, but it would be faster.

Answer 4

Because strings are immutable in Java, you will need at least one copy no matter what. Ans the best way you should bet on is to use character array and System.arraycopy. Another alternatives are StringBuilder/StringBuffer and CharBuffer. Hope this helps.

Answer 5

You should use a StringBuilder. However, here's a method which you can shoot yourself in the foot with:

 String s = "bookkeepers";
 Class<?> c = String.class;
 Field field = c.getDeclaredField("value");
 field.setAccessible(true);
 char[] value = (char[]) field.get(s);
 // remove duplicate characters
 char last = 0;
 int len = 0;
 int writePtr = 0;
 for(int i = 0; i < value.length; i++) {
  value[writePtr] = value[i];
  if (value[i] != last) {
   writePtr++;
   last = value[i];
   len++;
  }
 }
 Field count = c.getDeclaredField("count");
 count.setAccessible(true);
 count.set(s, len);

 System.out.println(s);

Output bokepers