✅ 100% Accepted | Easy Approach | JAVA & C++ 💎
IntuitionIntuition that i got is that...
That if i pick a character then what is the probability that the character will reappear in the future and it will give
![Screenshot 2025-01-21 at 5.56.12 PM.png](https://assets.leetcode.com/users/images/222672d4-ed1d-4a66-b175-14bb4612899d_1737462396.4398003.png)

# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
Intuition that i got is that...
That if i pick a character then what is the probability that the character will reappear in the future and it will give smallest lexico string 

# Approach

So , the problem is that how do i store the appearence of character in the future 

```
int[] freq = new int[26];
    int n = s.length();
    for(int i = 0 ; i < n ; i++){
        char c = s.charAt(i);
        freq[c - 'a'] = i ;
    }
```
this was sorted by this method of keeping the last index of the occurence of the character 

Now the next problem was that how to pick the smallest letter first such that all the characters appear after it that is if the string contains 'a' theres no guarentee that all the rest alphabets will appear in the future 

so this was solved by
Adding each letter in the string 
then checking if a character smaller than the last character has appeared 
if yes and it satisfies the condition that it appears again in the future then we can remove the last character and append the new character in the string 
and this is kept in the while loop as series of letters will be removed if a smaller letter appears 
For eg . 

```
while(sb.length() > 0 && sb.charAt(sb.length()-1) - c > 0 && (freq[sb.charAt(sb.length()-1) - 'a'] > i)){
    char toBeDeleted = sb.charAt(sb.length()-1);
    visited[toBeDeleted-'a'] = false ; 
    sb.deleteCharAt(sb.length()-1);
}
```
"bcdabcd" --> "bcd" is the result 
when 'a' appears and we check that the letter 'd' appears again in the future with the help of freq array 
then pop 'd' 
similarly we check this condtion with 'c' and 'b'
this loop leads to the removal of "bcd" and 'a' gets the first places 

thus we got the smallest lexicographical string 

Do this a dry run then you'll get it 
If helpful please upvote 
thank you 


<!-- Describe your approach to solving the problem. -->

# Complexity
- Time complexity:
$$O(n)$$

- Space complexity:
$$O(n)$$
# Code
```java []
class Solution {
    public String removeDuplicateLetters(String s) {
        int[] freq = new int[26];
        int n = s.length();
        for(int i = 0 ; i < n ; i++){
            char c = s.charAt(i);
            freq[c - 'a'] = i ;
        }

        boolean[] visited = new boolean[26];

        StringBuilder sb = new StringBuilder();

        for(int i = 0 ; i < n ; i++){
            char c = s.charAt(i);
            int idx = c - 'a';
            if(visited[idx] == false){
                while(sb.length() > 0 && sb.charAt(sb.length()-1) - c > 0 && (freq[sb.charAt(sb.length()-1) - 'a'] > i)){
                    char toBeDeleted = sb.charAt(sb.length()-1);
                    visited[toBeDeleted-'a'] = false ; 
                    sb.deleteCharAt(sb.length()-1);
                }
                sb.append(c);
                visited[idx] = true ;
            }
        }

        return sb.toString();
    }
}
```
```C++ []
class Solution {
public:
    string removeDuplicateLetters(string s) {
        int freq[26] = {0}; // Frequency array to track last index of each character
        int n = s.length();

        // Fill frequency array with the last index of each character
        for (int i = 0; i < n; i++) {
            freq[s[i] - 'a'] = i;
        }

        bool visited[26] = {false}; // Visited array to track if a character is already in the result
        string result;

        for (int i = 0; i < n; i++) {
            char c = s[i];
            int idx = c - 'a';

            // Skip if the character is already in the result
            if (visited[idx]) continue;

            // Remove characters from the result if:
            // - The result is not empty
            // - The last character in the result is greater than the current character
            // - The last character exists later in the string
            while (!result.empty() && result.back() > c && freq[result.back() - 'a'] > i) {
                char toBeDeleted = result.back();
                visited[toBeDeleted - 'a'] = false; // Mark as not visited
                result.pop_back(); // Remove the last character
            }

            // Add the current character to the result and mark it as visited
            result.push_back(c);
            visited[idx] = true;
        }

        return result;
    }
};
```
```java  []
class Solution {
    public String smallestSubsequence(String s) {
        //Monotonic Stack Usage 
        Stack<Character> st = new Stack<>();
        int n = s.length();
        //lastIndex 
        int[] lastIndex = new int[26];
        for(int i = 0 ; i < n ; i++){
            int idx = s.charAt(i) - 'a';
            lastIndex[idx] = i ; 
        }

        //Visited array so that we only add the character once
        boolean[] visited = new boolean[26];

        //Now we create the stack
        for(int i = 0 ; i < n ; i++){
            char c = s.charAt(i);
            int idx = c - 'a';
            if(visited[idx] == false){
                while(!st.isEmpty() && (st.peek() - c) > 0 && lastIndex[st.peek() - 'a'] > i){
                    visited[st.peek()-'a'] = false ;
                    st.pop();
                }
                st.push(c);
                visited[idx] = true ;
            }
        }

        //Now we take out the string from stack
        StringBuilder sb = new StringBuilder();
        while(!st.isEmpty()){
            sb.append(st.peek());
            st.pop();
        }
        return sb.reverse().toString();
    }
}
```




['Java']