Remove duplicate chars from string (c++)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75

/****************************************************************************************** ******************************************************************************************* Chapter 1 Arrays and Strings * Remove duplicate characters in a string. By: Hamed Kiani (July 15, 2015) ****************************************************************************************** ******************************************************************************************/ #include<iostream> #include<cstring> using namespace std; // remove inplace , time: O(n^2), additional space: O(1) void rem_dup_str(char *str) { // return if str is NULL or str.length< 2 if (!str) return; if (strlen(str) < 2) return; // end: keeps the end of the string with no dulicate, is initialized to 1. // i : is the counter on the str length // j looks for any duplicate char from the first char of string till "end"; // str[end] = '\0' sets the rest of string which may contain redundant chars int j, end = 1; for (int i = 1; str[i] != '\0' ; i++){ for (j = 0; j<end; j++) if (str[i] == str[j]) break; if (j == end) str[end++] = str[i]; // do not change the } str[end] = '\0'; } // remove by buffer , time: O(n), additional space: O(n) void rem_dup_str_buffer(char *str) { if (!str) return; // keep the end of non-duplicated string by "end" // dup[256] is true is the corresponding char was seen before // works for all ASCII chars. int end = 0; bool dup[256] = {false}; for (int i = 0; str[i] != '\0'; i++) { if (dup[(int) str[i]]) continue; else { dup[(int) str[i]] = true; str[end++] = str[i]; } } str[end] = '\0'; } // Test it! int main() { char str[] = "Remove dublicate chars from string!"; cout << "original str: " << str << endl; rem_dup_str_buffer(str); cout << "after removing duplicate chars: " << str << endl; return 0; }