Given a string of ASCII characters, write the write a program to remove the duplicate elements present in them. For example, if the given string is "Potato", then, the output has to be "Pota". Additional constraint is, the algorithm has to be in-place( no extra data structures allowed)
Idea for an O(n) solution :
Let’s start with ['a','b','a','c','a','a','d','b','c']
[i:j:'a','b','a','c','a','a','d','b','c'] – [0,0,0,0] (character map for a,b,c,d)
1st charcter is an ‘a’, it’s not in the map, so we add it and increment i&j
['a',i:j:'b','a','c','a','a','d','b','c'] – [1,0,0,0]
2nd character is ‘b’, same procedure as before
['a','b',i:j:'a','c','a','a','d','b','c'] – [1,1,0,0]
third character is an ‘a’, this is already in the map, so we clear the spot, and increment only i
['a','b',j:0,i:'c','a','a','d','b','c'] – [1,1,0,0]
fourth character is ‘c’, which is not in the map; since i and j are different we add ‘c’ to the map, move it to position j, clear position i and increment i and j.
['a','b','c',j:0,i:'a','a','d','b','c'] – [1,1,1,0]
fifth and sixth character are handled like the third
['a','b','c',j:0,0,0,i:'d','b','c'] – [1,1,1,0]
seventh character is ‘d’, which is not in the map, so we handle it like the fourth one.
['a','b','c','d',j:0,0,0,i:'b','c'] – [1,1,1,1]
last two are like third case.
['a','b','c','d',j:0,0,0,0,0]:i – [1,1,1,1]
i has incremented beyond the range of the array so we’re done. We have j unique characters starting from position 0.
Code :
public static void main(String[] args) {
char[] a = {‘a’,'b’,'a’,'c’,'a’,'a’,'d’,'b’,'c’};
boolean[] ascii = new boolean[256];
int j=0;
for(int i=0;i<255;i++){
ascii[i] = false;
}
for(int i=0; i
if(ascii[a[i]] == false)
{
ascii[a[i]] = true;
a[j] = a[i];
if (i != j)
{
a[i] = ‘0′;
}
j++;
i++;
}
else if (ascii[a[i]] == true)
{
a[j]=’0′;
a[i]=’0′;
i++;
}
}
0 comments:
Post a Comment