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:
packagecrack.coding.interview;
public classRemoveDuplicate {
/**
* Remove Duplicate using extra memory space.
* @param str
*/
public static voidremoveDuplicatesEff(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 voidmain(String[] args) {
String str = "removeduplicate";
char[] array = str.toCharArray();
removeDuplicatesEff(array);
System.out.println(newString(array));
}
}
Using only one extra variable:
packagecrack.coding.interview;
public classRemoveDuplicate {
private static voidremoveDuplicate(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 voidmain(String[] args) {
String str = "removeduplicate";
char[] array = str.toCharArray();
removeDuplicate(array);
System.out.println(newString(array));
}
}
No comments:
Post a Comment