Algorithm Puzzles: Remove Duplicate Letters

Posted on Edited on In Views: Word count in article: 140 Reading time ≈ 1 mins.

Algorithm Puzzles everyday every week sometimes: Remove Duplicate Letters

Puzzle

Puzzle from leetcode:

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.

Solution

MonotonicStack

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
 public:
  std::string removeDuplicateLetters(const std::string& s) const {
    int lastOccur[26] = {-1};
    size_t len = s.length();
    int visited[26] = {0};
    std::stack<int> stk = {};
    std::string ret = "";

    for (int i = 0; i < len; ++i) {
      lastOccur[s[i] - 'a'] = i;
    }

    for (int i = 0; i < len; ++i) {
      if (visited[s[i] - 'a'] == 0) {
        while (!stk.empty() && s[stk.top()] > s[i] &&
               lastOccur[s[stk.top()] - 'a'] > i) {
          visited[s[stk.top()] - 'a'] = 0;
          stk.pop();
        }
        stk.push(i);
        visited[s[i] - 'a'] = 1;
      }
    }

    while (!stk.empty()) {
      ret = s[stk.top()] + ret;
      stk.pop();
    }

    return ret;
  }
};

T.C: O(N*N)