[15 Feb 2020] Remove duplicates from a string in O(1) extra space

Remove duplicates from a string in O(1) extra space

Given a string str of lowercase characters, the task is to remove duplicates and return a resultant string without modifying the order of characters in the original string.

Examples:

Input: str = "geeksforgeeks"
Output: geksfor

Input: str = "characters"
Output: chartes

Approach: The idea is to use bits of a counter variable to mark the presence of a character in the string. To mark the presence of ‘a’ set 0th bit as 1, for ‘b’ set 1st bit as 1 and so on. If the corresponding bit of character present in the original string is set to 0, it means it is the first occurrence of that character, hence set its corresponding bit as 1 and keep on including the current character in the resultant string.

// C++ implementation of above approach #include <bits/stdc++.h> #include <string> using namespace std;    // Function to remove duplicates string removeDuplicatesFromString(string str) {        // keeps track of visited characters     int counter = 0;        int i = 0;     int size = str.size();        // gets character value     int x;        // keeps track of length of resultant string     int length = 0;        while (i < size) {         x = str[i] - 97;            // check if Xth bit of counter is unset         if ((counter & (1 << x)) == 0) {                str[length] = 'a' + x;                // mark current character as visited             counter = counter | (1 << x);                length++;         }         i++;     }        return str.substr(0, length); }    // Driver code int main() {     string str = "geeksforgeeks";     cout << removeDuplicatesFromString(str);     return 0; }

Output:

geksfor

Time Complexity: O(n)
Space Complexity: O(1)

// Java implementation of above approach import java.util.Arrays;    class GFG {        // Function to remove duplicates     static char[] removeDuplicatesFromString(String string)     {            // keeps track of visited characters         int counter = 0;         char[] str = string.toCharArray();         int i = 0;         int size = str.length;            // gets character value         int x;            // keeps track of length of resultant String         int length = 0;            while (i < size) {             x = str[i] - 97;                // check if Xth bit of counter is unset             if ((counter & (1 << x)) == 0) {                    str[length] = (char)('a' + x);                    // mark current character as visited                 counter = counter | (1 << x);                    length++;             }             i++;         }            return Arrays.copyOfRange(str, 0, length);     }        // Driver code     public static void main(String[] args)     {         String str = "geeksforgeeks";         System.out.println(removeDuplicatesFromString(str));     } }    // This code is contributed by Mithun Kumar

Output:

geksfor

Time Complexity: O(n)
Space Complexity: O(1)

# Python3 implementation of above approach    # Function to remove duplicates def removeDuplicatesFromString(str2):        # keeps track of visited characters     counter = 0;        i = 0;     size = len(str2);     str1 = list(str2);        # gets character value     x = 0;        # keeps track of length of resultant string     length = 0;        while (i < size):         x = ord(str1[i]) - 97;            # check if Xth bit of counter is unset         if ((counter & (1 << x)) == 0):             str1[length] = chr(97 + x);                # mark current character as visited             counter = counter | (1 << x);                length += 1;         i += 1;                str2=''.join(str1);     return str2[0:length];    # Driver code str1 = "geeksforgeeks"; print(removeDuplicatesFromString(str1));    # This code is contributed by mits

Output:

geksfor

Time Complexity: O(n)
Space Complexity: O(1)