
### Problem Statement

###### Given a string s, remove duplicate letters so that every letter appears once and only once. You must make sure your result is the smallest in lexicographical order among all possible results.

**INPUT**

- **s = "cbacdcbc"**

**OUTPUT**

- **"acdb"**

**Steps To Solve**

- As per the given problem statement we have to remove the duplicates and make sure that our result is in lexicographical order
- Come to the implementation, we need some data structure to store the previous characters and we need to compare the current character with previous saved ones, and if there are multiple same characters, we prefer left ones. This calls for a stack.
- Lets understand how stack fits as a goto data structure for these types of problems.
- Take the above example **"cbacdcbc"**.
- Insert the first character **c** into the empty stack.
- Also keep a boolean array **seen** to mark already visited characters.
- If we come across **c** again we can check it in **seen** array and do not add it again into the stack.
- Then we come across **b** , we see that **c** is lexicographical greater than **b** , so we can remove **c** from the stack to maintain lexicographical order but we have to make sure that there are more **c** present in the later part of the string that comes after **b**.
- To do this we traverse the string once before doing all this and store the last index of every character in the string.
- So the last occurance of **c** is at index 7 and now we are at index 1 , that means we can remove **c** from stack and push **b**.
- After removal of **c** we will reset the value of **c** in the **seen** array to **false** , as **c** does not matter to us anymore.
- When we reach **a** at 2nd index , we do the same thing and remove **b** as **b** is lexicographical greater than **a**.
- We we reach **c** at 3rd index we see that **c** is lexicographical greater than **a** , which is fine and hence we add that to our stack.
- Then we will add **d** as it satisfies all the requirements.
- We then come across another **c** at index 5 , as we have **c** in stack we will ignore this **c** and continue our loop.
- Then we reach **b** , we see that **b** is lexicographical smaller than **d** , but we cannot remove it as we don't have any more **d** in the following string. So we add **b** after **d**.
- Finally, we will ignore the last **c** as **c** is already present in the stack.
- Our stack now contains values **a,c,d,b**.
- We will now pop every value from our stack and append to string one by one.
- Finally, we will reverse the string to get the final result.
- Moving on to solution...

```js
/**
 * @param {string} s
 * @return {string}
 */
var removeDuplicateLetters = function (s) {
  const seen = new Array(26).fill(false);
  const lastIndex = new Array(26).fill(-1);

  let result = "";

  const stack = new Stack();

  for (const idx in s) {
    const ASCII = getASCII(s[idx]);
    lastIndex[ASCII] = +idx;
  }

  for (const idx in s) {
    const ASCII = getASCII(s[idx]);
    if (seen[ASCII]) continue;

    while (
      !stack.isEmpty() &&
      stack.top() > ASCII &&
      idx < lastIndex[stack.top()]
    ) {
      seen[stack.pop()] = false;
    }

    stack.push(ASCII);
    seen[ASCII] = true;
  }

  while (!stack.isEmpty()) {
    result += fromASCII(stack.pop());
  }

  return revString(result);
};

function fromASCII(s) {
  return String.fromCharCode(97 + s);
}

function revString(s) {
  return s?.split("").reverse().join("");
}

function getASCII(s) {
  return s.charCodeAt(0) - 97;
}

class Stack {
  stack;
  constructor() {
    this.stack = [];
  }

  get length() {
    return this.stack.length;
  }

  isEmpty() {
    return this.stack.length === 0;
  }

  pop() {
    let temp = this.stack[this.stack.length - 1];
    this.stack.length = this.stack.length - 1;
    return temp;
  }

  top() {
    return this.stack[this.stack.length - 1];
  }

  push(item) {
    this.stack.push(item);
  }
}
```

###### Time and Space Complexity

Time Complexity is **O(N)**.
Space complexity is **O(26)** or **O(1)**.
