# 26- Remove Duplicate Letters

The problem can be found at the following link: [Question Link](https://leetcode.com/problems/remove-duplicate-letters/description/)

## My Approach

1. Initialize two vectors:
   * `freq`: A vector of size 26 to keep track of the frequency of each lowercase letter in the input string `s`. Initialize all elements to 0.
   * `visited`: A vector of size 26 to keep track of whether a character has been visited or not. Initialize all elements to 0.
2. Iterate through the characters of the input string `s`:
   * For each character `ch` in `s`, increment the corresponding frequency in the `freq` vector. This will count how many times each character appears in the string.
3. Initialize an empty string `ans` to store the result.
4. Get the length of the input string `s` and store it in a variable `n`.
5. Iterate through the characters of the input string `s` again using a loop from `i=0` to `i<n`:
   * Decrement the frequency of the current character `s[i]` in the `freq` vector.
6. Check if the current character `s[i]` has not been visited yet (i.e., `visited[s[i]-'a']` is 0):
   * Enter a while loop that continues as long as the following conditions are met:
     * `ans` is not empty (`ans.size()` is non-zero).
     * The last character in `ans` (i.e., `ans.back()`) is greater than the current character `s[i]`.
     * The frequency of the last character in `ans` is greater than 0 (i.e., `freq[ans.back()-'a'] > 0`).
   * Inside the while loop:
     * Mark the character as not visited by setting `visited[ans.back()-'a']` to 0.
     * Remove the last character from `ans` by using `ans.pop_back()`.
7. After exiting the while loop, append the current character `s[i]` to the `ans` string to add it to the result.
8. Mark the current character `s[i]` as visited by setting `visited[s[i]-'a']` to 1.
9. Repeat steps 5-8 for all characters in the input string `s`.
10. Return the final `ans` string, which contains the unique characters from the input string in lexicographically smallest order while maintaining their relative order.

## Time and Auxiliary Space Complexity

* Time Complexity: `O(n)`
* Auxiliary Space Complexity: `O(n)`

## Code (C++)

```cpp

class Solution {
public:
    string removeDuplicateLetters(string s) {
      vector<int>freq(26,0), visited(26,0);
        for(auto ch:s)freq[ch-'a']++;

        string ans;
        int n = s.length();
        for(int i=0;i<n;i++){
               freq[s[i]-'a']--;
               if(!visited[s[i]-'a']){ 
                while(ans.size() and ans.back()>s[i] and freq[ans.back()-'a']>0) {
                    visited[ans.back()-'a'] = 0;
                    ans.pop_back();
                }
                ans.push_back(s[i]);
                visited[s[i]-'a'] = 1;
                }
        }
        return ans;
    }
};

```

## Contribution and Support

For discussions, questions, or doubts related to this solution, please visit our [discussion section](https://leetcode.com/discuss/general-discussion). We welcome your input and aim to foster a collaborative learning environment.

If you find this solution helpful, consider supporting us by giving a `⭐ star` to the [rishabhv12/Daily-Leetcode-Solution](https://github.com/rishabhv12/Daily-Leetcode-Solution) repository.