Remove duplicate characters in a string This is a question from the book "Cracking the Coding Interview".


  Design an algorithm and write code to remove the duplicate characters
  in a string without using any additional buffer NOTE: One or two
  additional variables are fine An extra copy of the array is not


This is not the efficient code, but I want to preserve the order of characters after deleting duplicate characters.

#include &lt;iostream&gt;
#include &lt;string&gt;
#include &lt;cctype&gt; //std::toupper, std::tolower

void removeDuplicates(std::string&amp; str)
{
    int flag = 0;
    int len = str.length();
    for (int i = 0; i &lt; len - 1; ++i)
    {
        for (int j = i + 1; j &lt; len - 1; ++j)
        {
            if (str[i] == std::toupper(str[j])
                || str[i] == std::tolower(str[j]))
            {
                str.erase(str.begin() + j);
                flag = 1;
            }
        }
    }
    if (flag == 0)
    {
        std::cout &lt;&lt; "There are no duplicate characters\n";
    }
    else
    {
        std::cout &lt;&lt; "There are duplicate characters\n";
    }
}

int main()
{
    std::string str;
    std::cout &lt;&lt; "Enter String\n";
    std::getline(std::cin, str);
    removeDuplicates(str);
    std::cout &lt;&lt; "New String\n";
    std::cout &lt;&lt; str &lt;&lt; '\n';
}


Help me optimize this code.
Clarify the requirement

You state 'remove duplicate characters' but then your code checks for upper and lower case matches - is the requirement to check for distinct letters, or distinct characters? 

Sort out the bugs

I sense premature optimisation here, and it is the root of some evil:

int len = str.length();
for (int i = 0; i &lt; len - 1; ++i)
{
    for (int j = i + 1; j &lt; len - 1; ++j)
    {
        if (str[i] == std::toupper(str[j])
            || str[i] == std::tolower(str[j]))
        {
            str.erase(str.begin() + j);
            flag = 1;
        }
    }
}


What is the value of len? The length of the original string. And what is the value of len after we have erased a duplicate character? Still the same. So if we do find some duplicates, we will then happily run out of bounds in both loops. You can manually update len, or you could just call length() - it is constant complexity so you aren't rescanning the string each time. I would opt for comparing to length() until a profiler tells you otherwise.

Getting an idea of computational complexity

The complexity of the pair of loops is O(n2). But inside that, you do an erase - imagine we erase from the middle of the string (which is the average case); then we will need to copy about n/2 characters into the previous positions. This gives us O(n3).

There are things we can do to improve a bit - we can continue scanning for further duplicates before erasing, so that abccccccccd only required one copy, collecting all the duplicate c in one go.

Without preserving order, we can do O(n log n)

The easy way to improve the complexity is just to sort the characters in the string: 

std::sort(str.begin(), str.end());


And then run through removing adjacent duplicates. 

Is it possible to remove duplicates with O(n log n) (or better) complexity whilst maintaining order?

Consider the decision whether to elide some character halfway through the string. This character could be any of (assuming 1 byte chars) 256 values, so the bare minimum storage needed to make the decision is 256 bits. The requirements are not clear - 'one or two additional variables' could easily cover a 256 element std::bitset (should be 64 bytes), but could also not cover it if they are angling for a specific solution.

If we can keep that std::bitset, then we can mark each byte value that we've seen in the array and erase any contiguous blocks of duplicates we see. Marking a value in a fixed size array is constant time (O(1)), so the cost of detecting whether each character is a duplicate is still only O(n). But if we erase them each time we find them, we will end up in O(n2) land again, copying the last character in the string into successive locations. 

Remove_if to the rescue

There is a way to remove all those duplicates without copying each later character more than once; imagine two position markers, one to the character we are assessing, and one to an earlier position at the end of the deduplicated string. If we copy each character directly into it's final position then the space left by duplicate characters will bubble to the end:

abcdeaafg_
    ^^
abcdeaafg_
    ^ ^
abcdefafg_
     ^ ^
abcdefgfg_
      ^ ^
abcdefg_


But instead of having to cope with all the details, we can call remove_if, which does just that job for us, at a cost of n calls to the predicate. The predicate (boolean test function) will look up the character value in the bitset:

static_assert((CHAR_MAX - CHAR_MIN &lt;= 256), "Implementation requires 8 bit char");
std::bitset&lt;256&gt; seenChars;
auto newEnd = remove_if(str.begin(), str.end(),
   [&amp;seenChars](auto &amp; c) {    // capture seenChars so we can use it
       if(seenChars[c%256])   // have seen it before, so remove
           return true;
       seenChars[c%256] = true; // we have seen it now
       return false;             // but we won't remove this one
    });


(Edited this after replacing array with bitset)

To unpack that a little: we are removing any character for which the predicate returns true. The predicate simply checks whether the character has been seen (by casting the character to int and using it modulo 256 as the index into the bitset), and either returns true or marks this character value for next time and returns false. The [&amp;seenChars] captures the bitset so that we can use it inside the predicate without having to pass it in; it forms part of the context of the function body.

The hardcoded 256 is not ideal, perhaps, although I wouldn't want to make it general to larger numbers (instead just failing a static_assert) because of the implication for storage.

remove_if itself returns an iterator to the new end position of the string; it has copied the latter values into the earlier positions, but not resized the string. We resize, then:

str.resize(std::distance(str.begin(), newEnd));


Et voila, we have removed duplicates, in place, with a space requirement of 256 bits and a time complexity of O(n). Not too shabby.

By the way, you can detect the removal of duplicates by comparing the original string length with the final string length. If they differ, duplicates were indeed found.