Greedy: Remove duplicates from a string

Problem Statement:

You are given a string s, you need to remove duplicate letters so that every letter should appear only once.

The result should be in smallest lexicographical order

Example

Input: s = “bcabcccdd”
Output: “abcd”

Solution

The solution is very simple:

1. First we count the frequency of each character.

2. Then we traverse the string and check if the char has been inserted in the result. If it is, we will skip the char.

3. When the result.back() is larger than the current char, we check if the result.back() is present in latter substring.

If we can still find it later, we can pop it from the back and add it later.

4. Add the current char to the back of the result string.

5. set visited[current_char] = true.

Solution in C++

#include<iostream>
#include<vector>
#include<algorithm>
#include<unordered_set>

using namespace std;

string removeDuplicateLetters(string s) 
{
    vector<int> cand(256, 0);
    vector<bool> visited(256, false);

    for (char c : s)
        cand[c]++;

    string result = "0";

    for (char c : s) 
    {
        cand[c]--;
        if (visited[c]) 
         continue;
        
        while (c < result.back() && cand[result.back()]) 
        {
            visited[result.back()] = false;
            result.pop_back();
        }
        result += c;
        visited[c] = true;
    }
    return result.substr(1);
}

int main()
{
   char str[]= "bcabc";
   cout << removeDuplicateLetters(str);
   return 0;
}

Output:

abc