Design
an algorithm and write code to remove the duplicate characters in a string without using any additional buffer.
To solve this problem, we can apply the same approach as we used to check the unique character in the string. Please check for the unique character in the string for better understanding of below given solution.
Using one Boolean array:
package
crack.coding.interview;
public class
RemoveDuplicate {
/**
* Remove Duplicate using extra memory space.
* @param str
*/
public static void
removeDuplicatesEff(char[] str) {
int len = 0;
if (str == null ||
(len = str.length)<2) {
return;
}
boolean[]
map = new boolean[256];
for (int i = 1; i
< len; ++i) {
if (!map[str[i]])
{
map[str[i]]
= true;
} else {
str[i] =
'0';
}
}
}
/**
* Driver method top remove duplicate.
* @param args
*/
public static void
main(String[] args) {
String str = "removeduplicate";
char[]
array = str.toCharArray();
removeDuplicatesEff(array);
System.out.println(new
String(array));
}
}
Using only one extra variable:
package
crack.coding.interview;
public class
RemoveDuplicate {
private static void
removeDuplicate(char[] array) {
int map = 0;
for (int i = 0; i
< array.length; i++) {
int val =
array[i] - 'a';
/* Shift for Map bit position.
* Exp: For b val= 1 and the bit position after
shifting 10,
* For c val= 2 and the bit position after
shifting 100 */
int bitPos =
1 << val;
/* Check whether bit position already 1.
* If true: Set duplicate bit to zero. */
if((map
& bitPos)>0) {
array[i]
= '0';
}
/* Modify the bit position in the array. */
map = map |
bitPos;
}
}
/**
* Driver method top remove duplicate.
* @param args
*/
public static void
main(String[] args) {
String str = "removeduplicate";
char[]
array = str.toCharArray();
removeDuplicate(array);
System.out.println(new
String(array));
}
}
No comments:
Post a Comment