Advertisement
Guest User

Untitled

a guest
Feb 17th, 2019
89
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.24 KB | None | 0 0
  1. class Solution {
  2. public:
  3.     string removeDuplicateLetters(const string& s) {
  4.         fill_n(last_index_.begin(), kRadix, s.size());
  5.         fill_n(used_.begin(), kRadix, false);
  6.         all_occurences_ = vector<vector<int>>(kRadix, vector<int>());
  7.  
  8.         for (int i = 0; i < s.size(); ++i) {
  9.             all_occurences_[s[i] - 'a'].push_back(i);
  10.             last_index_[s[i] - 'a'] = i;
  11.         }
  12.  
  13.         int chars_left = 0;
  14.         for (int i = 0; i < kRadix; ++i) {
  15.             if (last_index_[i] != s.size()) ++chars_left;
  16.             else used_[i] = true;
  17.         }
  18.  
  19.         string res = "";
  20.  
  21.         while (chars_left) {
  22.             for (int i = 0; i < kRadix; ++i) {
  23.                 if (used_[i]) continue;
  24.  
  25.                 for (auto pos : all_occurences_[i]) {
  26.                     if (CanTakeAsNext(pos)) {
  27.                         res += ('a' + i);
  28.                         used_[i] = true;
  29.                         --chars_left;
  30.                         break;
  31.                     }
  32.                 }
  33.                 if (used_[i]) break;
  34.             }
  35.         }
  36.  
  37.         return res;
  38.     }
  39.  
  40. private:
  41.     static constexpr int kRadix = 26;
  42.  
  43.     array<int, kRadix> last_index_;
  44.     vector<vector<int>> all_occurences_;
  45.     array<bool, kRadix> used_;
  46.     mutable int min_index_{ -1 };
  47.  
  48.     bool CanTakeAsNext(int pos) const {
  49.         if (pos < min_index_) return false;
  50.  
  51.         for (int i = 0; i < kRadix; ++i) {
  52.             if (!used_[i] && last_index_[i] < pos)
  53.                 return false;
  54.         }
  55.  
  56.         min_index_ = pos;
  57.         return true;
  58.     }
  59. };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement