Problem BreakDown || Intuition Explained || Java
Similar solution on 316 leetcodeProblem BreakdownWhat is Lexicographically Smaller ?A string a is lexicographically smaller than a string b if in the first posi
##   Similar solution on [316 leetcode](https://leetcode.com/problems/remove-duplicate-letters/solutions/6587779/problem-breakdown-intuition-explined-ja-wwdy/)
# Problem Breakdown 
#### What is Lexicographically Smaller ?
A string `a` is lexicographically smaller than a string b if in the first position where `a` and `b` differ, string `a` has a letter that appears earlier in the alphabet than the corresponding letter in `b`.
If the first `min(a.length, b.length)` characters do not differ, then the shorter string is the lexicographically smaller one.
##### Example
Starting with **c**
"**cba**c**d**cbc" = "cbad"
"**c**b**a**c**d**c**b**c" = "cadb"
Starting with **b**
"c**bacd**cbc" = "bacd"
"c**ba**c**dc**bc" = "badc"
"c**ba**c**d**cb**c**" = "badc" duplicate result
Starting with **a**
"cb**acd**c**b**c" = "acdb"
"cb**a**c**dcb**c" = "adcb"
"cb**a**c**d**c**bc**" = "adbc"

and once we arrange them lexicographically...
"acdb"
"adbc"
"adcb"
"bacd"
"badc"
"badc"
"cadb"
This is the Problem statement actually.
# Intuition
What we need to take care of ?
- We should check whether a character is in the stack or not - Boolean array is efficient than hashset in this scenario.
- Every element should occur once so on a long run check if current char is available later or not (in lexicographical ordering currently we may remove it but may not get later) - int array 
- Comparing adjacent character - stack

<!-- Describe your first thoughts on how to solve this problem. -->

# Approach
- Initialise a stack to store the characters lexicographically
- Initialise an int array vis to keep track of last available index of a character
- Initialise a boolean array to check if a current char is in stack or not
- Iterate over the string 
  - update the vis array
- Iterate over the string
  - if it is already in stack continue;
  - While stack is not empty AND top of stack is more than the current element and is available in future 
    - pop it from stack
    - mark it as unvisited
  - push the char to stack
  - mark it as visited
- Construct a stringBuilder sb
  - pop all the chars and append to the string
- reverse the string and return it 
<!-- Describe your approach to solving the problem. -->

# Complexity
- Time complexity:  $$O(n)$$ where `n` is length of the string
  - For computing last array - $$O(n)$$
  - Iterating over string and storing in stack - $$O(n)$$
  - Building String - $$O(26)$$ at max it would store 26 characters 
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity: $$O(1)$$
  - Stack st at maximum stores 26 characters  $$O(26)$$ ~  $$O(1)$$
  - int last array is of  $$O(26)$$ ~  $$O(1)$$
  - boolean vis array is of  $$O(26)$$ ~  $$O(1)$$
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```java []
class Solution {
    public String removeDuplicateLetters(String s) {
        Stack<Character> st = new Stack<>();
        int [] last = new int[26];
        boolean [] vis = new boolean[26];
        for(int i=0;i<s.length();i++){
            last[s.charAt(i)-'a']=i;
        }
        for(int i=0;i<s.length();i++){
            char c = s.charAt(i);
            if(vis[c-'a']==true)continue;
            while(!st.isEmpty()&&st.peek()>c&&last[st.peek()-'a']>i){
                vis[st.pop()-'a']=false;
            }
            st.push(c);
            vis[c-'a']=true;
        }
        StringBuilder sb= new StringBuilder();
        while(!st.isEmpty()){
            sb.append(st.pop());
        }
        return sb.reverse().toString();
    }
}
```
['String', 'Stack', 'Greedy', 'Monotonic Stack', 'Java']