Given a string, Write a program to remove duplcate characters from the string.
Input String : crazyforcode
Output String : crazyfode
Algorithm :
1. For each character, check if it is duplicate of already found characters.
2. Skip duplicate characters and update the non duplicate characters.
Method 1 Using Extra Space.
void removeDuplicates(char *str)
{
if (!str)
return;
int len = strlen(str);
if (len < 2)
return;
bool hit[256];
for(int i = 0; i < 256; ++i)
hit[i] = false;
hit[str[0]] = true;
int tail = 1;
for (int i = 1; i < len; ++i)
{
if (!hit[str[i]])
{
str[tail] = str[i];
++tail;
hit[str[i]] = true;
}
}
str[tail] = '\0';
}
Time Complexity : O(N)
Method 2 : Without using extra space.
void removeDuplicates(char *str)
{
if (!str)
return;
int len = strlen(str);
if (len < 2)
return;
int tail = 1;
for (int i = 1; i < len; ++i)
{
int j;
for (j = 0; j < tail; ++j)
if (str[i] == str[j])
break;
if (j == tail)
{
str[tail] = str[i];
++tail;
}
}
str[tail] = '\0';
}
Time Complexity : O(N^2)
bool hit[256];
for(int i = 0; i < 256; ++i)
hit[i] = false;
Instead of above code just nelow will work
bool hit[256] = {0} ;
Yes Amit. Your code would just work fine. Used for loop to make it more clear.
This can be done in O(nlogn).
First sort the array using quick sort.
Than compare each char with next char until repeated.
Yes.It can be done in O(nlogn) but after sorting order of characters won’t remain same.
if characters lies in the range a…z, then we can use following O(n) method without using extra space :
public static void removeDuplicates(char[] str) {
int map = 0;
for (int i = 0; i < str.length; i++) {
if ((map & (1 < 0) // duplicate detected
str[i] = 0;
else // add unique char as a bit ’1′ to the map
map |= 1 << (str[i] – 'a');
}
}
(borrowed from kodeknight)
I think the second method with complexity O(n ^ 2) can remove consecutive duplicates. for example it can convert abcdddefgg to abcdefg but it can not convert abcdefab to abcdef though the first one would do it.
have you given it a thought ??
why what is the difference?
can you please explain
public class Anagram {
public static void main(String[] args) {
String s1=”asdfas” ;
char [] arr=new char[256];
System.out.println();
for(int i=0;i<s1.length();i++)
{
arr[s1.charAt(i)]++;
}
for(int i=0;i1)
arr[i]–;
if(arr[i] == 1)
System.out.printf(“%c”,i);
}
}
}
hey can u elaborate the logic used??