1-3-edi5-removeDuplicates Algorithm
The 1-3-edi5-removeDuplicates Algorithm is an efficient technique for removing duplicate elements from an array, list, or other linear data structures. It works by iterating through the elements of the data structure and maintaining a separate index for unique elements. As it encounters each element, it checks if the element has already been seen. If the element is unique, it is added to the unique index, effectively overwriting any previously encountered duplicates. This process continues until all the elements have been checked. The algorithm is particularly useful when working with large data sets, where manually removing duplicates would be time-consuming and error-prone.
One of the primary advantages of the 1-3-edi5-removeDuplicates Algorithm is its in-place operation, which means it does not require any additional memory allocation to perform its function. This makes it an ideal choice for applications with limited memory resources or when working with large data sets. Additionally, the algorithm has a linear time complexity of O(n), where n is the number of elements in the data structure. This means that the algorithm's performance scales linearly with the size of the input, making it a highly efficient solution for removing duplicates from a wide range of data structures.
/*
* Cracking the coding interview, edition 5
* Problem 1.3
* Write an algorithm to remove duplicate chars from a string
*/
#include <iostream>
#include <cstring>
using std::string;
using std::cin;
using std::cout;
using std::endl;
/*
* Function - removeDuplicates1
* Args - A string
* Return - Arg string with no duplicate chars
* Runtime - O(n)
* Assumption - contains letter ( a - z )
*/
string removeDuplicates1( const string & str )
{
int len = str.length();
if ( len < 2 ) {
return str;
}
int check = 0;
string result("");
for ( auto & ch : str ) {
int c = (int)( ch - 'a');
if ( (check & ( 1 << c )) == 0) {
result += ch;
check |= ( 1 << c);
}
}
return result;
}
/*
* Function - removeDuplicates2
* Args - A string
* Return - Arg string with no duplicate chars
* Runtime - O(n)
* Assumption - ASCII extended char set
*/
string removeDuplicates2 ( const string & str )
{
int len = str.length();
if ( len < 2 )
return str;
string result("");
bool check[256];
for ( auto & ch : str ) {
if ( !check[(int)ch] ) {
check[(int)ch] = true;
result += ch;
}
}
return result;
}
/*
* Function - removeDuplicates3
* Args - A string
* Return - Arg string with no duplicate chars
* Runtime - O(n^2)
* Assumption - NONE
*/
string removeDuplicates3( string str )
{
int len = str.length();
if ( len < 2 ) {
return str;
}
string result("");
for ( int i = 0; i < len; ++i) {
if ( str[i] != '\0' ) {
result += str[i];
for ( int j = i + 1; j < len; ++j ) {
if ( str[i] == str[j] ) {
str[j] = '\0';
}
}
}
}
return result;
}
/*
* Function - removeDuplicates4
* Args - A C string
* Return - void, we change the char array we pass as arg
* Runtime - O(n)
* Assumption - contains letter ( a - z )
*/
void removeDuplicates4( char * str )
{
int len = std::strlen(str);
if ( len < 2) {
return;
}
int check = 0;
int cindx = 0;
for ( int i = 0; i < len; ++i) {
int c = (int) ( str[i] - 'a');
if ( (check & ( 1 << c )) == 0 ) {
str[cindx++] = str[i];
check |= ( 1 << c );
}
}
str[cindx] = '\0';
}
/*
* Function - removeDuplicates5
* Args - A c string
* Return - void, we change the c-string we pass to function
* Runtime - O(n^2)
* Assumption - NONE
*/
void removeDuplicates5( char * str )
{
int len = std::strlen(str);
if ( len < 2 ) {
return;
}
int idx = 0;
for ( int i = 0; i < len; ++i) {
if ( str[i] != '\0' ) {
str[idx++] = str[i];
for ( int j = i + 1; j < len; ++j ) {
if ( str[i] == str[j] ) {
str[j] = '\0';
}
}
}
}
}
/*
* Function - removeDuplicates6
* Args - A c string
* Return - void, we change the c-string we pass to function
* Runtime - O(n)
* Assumption - ASCII extended char set
*/
void removeDuplicates6 ( char *str )
{
int len = std::strlen(str);
if ( len < 2 )
return;
bool check[256] = {false};
int idx = 0;
for ( int i = 0; i < len; ++i )
{
if ( !check[(int)str[i]] ) {
check[(int)str[i]] = true;
str[idx++] = str[i];
}
}
str[idx] = '\0';
}
int main()
{
string str1("aaaabbbbbcddeffgheee");
string str2("abcd");
string str3("a");
string str4("");
cout << "For method 1:" << endl;
cout << "original-string:" << str1 << " after removing duplicates:" << removeDuplicates1(str1) << endl;
cout << "original-string:" << str2 << " after removing duplicates:" << removeDuplicates1(str2) << endl;
cout << "original-string:" << str3 << " after removing duplicates:" << removeDuplicates1(str3) << endl;
cout << "original-string:" << str4 << " after removing duplicates:" << removeDuplicates1(str4) << endl;
cout << "\n\nFor method 2:" << endl;
cout << "original-string:" << str1 << " after removing duplicates:" << removeDuplicates2(str1) << endl;
cout << "original-string:" << str2 << " after removing duplicates:" << removeDuplicates2(str2) << endl;
cout << "original-string:" << str3 << " after removing duplicates:" << removeDuplicates2(str3) << endl;
cout << "original-string:" << str4 << " after removing duplicates:" << removeDuplicates2(str4) << endl;
cout << "\n\nFor method 3:" << endl;
cout << "original-string:" << str1 << " after removing duplicates:" << removeDuplicates3(str1) << endl;
cout << "original-string:" << str2 << " after removing duplicates:" << removeDuplicates3(str2) << endl;
cout << "original-string:" << str3 << " after removing duplicates:" << removeDuplicates3(str3) << endl;
cout << "original-string:" << str4 << " after removing duplicates:" << removeDuplicates3(str4) << endl;
cout << "\n\nFor method 4:" << endl;
char str5[] = "aaaabbbbcccc";
char str6[] = "abcde";
char str7[] = "a";
char str8[] = "";
cout << endl;
cout << "original-string:" << str5 << " after removing duplicates:";
removeDuplicates4(str5);
cout << str5 << endl;
cout << "original-string:" << str6 << " after removing duplicates:";
removeDuplicates4(str6);
cout << str6 << endl;
cout << "original-string:" << str7 << " after removing duplicates:";
removeDuplicates4(str7);
cout << str7 << endl;
cout << "original-string:" << str8 << " after removing duplicates:";
removeDuplicates4(str8);
cout << str8 << endl;
cout << "\n\nFor method 5:" << endl;
char str9[] = "aaaabbbbccccdddeeefffaaabbb";
char str10[] = "abcdef";
char str11[] = "b";
char str12[] = "";
cout << endl;
cout << "original-string:" << str9 << " after removing duplicates:";
removeDuplicates5(str9);
cout << str9 << endl;
cout << "original-string:" << str10 << " after removing duplicates:";
removeDuplicates5(str10);
cout << str10 << endl;
cout << "original-string:" << str11 << " after removing duplicates:";
removeDuplicates5(str11);
cout << str11 << endl;
cout << "original-string:" << str12 << " after removing duplicates:";
removeDuplicates5(str12);
cout << str12 << endl;
cout << "\n\nFor method 6:" << endl;
char str13[] = "aaaabbbbccccdddeeefffaaabbb";
char str14[] = "abcdef";
char str15[] = "b";
char str16[] = "";
cout << endl;
cout << "original-string:" << str13 << " after removing duplicates:";
removeDuplicates6(str13);
cout << str13 << endl;
cout << "original-string:" << str14 << " after removing duplicates:";
removeDuplicates6(str14);
cout << str14 << endl;
cout << "original-string:" << str15 << " after removing duplicates:";
removeDuplicates6(str15);
cout << str15 << endl;
cout << "original-string:" << str16 << " after removing duplicates:";
removeDuplicates6(str16);
cout << str16 << endl;
cout << endl;
return 0;
}
