Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- class Solution {
- public:
- string removeDuplicateLetters(const string& s) {
- fill_n(last_index_.begin(), kRadix, s.size());
- fill_n(used_.begin(), kRadix, false);
- all_occurences_ = vector<vector<int>>(kRadix, vector<int>());
- for (int i = 0; i < s.size(); ++i) {
- all_occurences_[s[i] - 'a'].push_back(i);
- last_index_[s[i] - 'a'] = i;
- }
- int chars_left = 0;
- for (int i = 0; i < kRadix; ++i) {
- if (last_index_[i] != s.size()) ++chars_left;
- else used_[i] = true;
- }
- string res = "";
- while (chars_left) {
- for (int i = 0; i < kRadix; ++i) {
- if (used_[i]) continue;
- for (auto pos : all_occurences_[i]) {
- if (CanTakeAsNext(pos)) {
- res += ('a' + i);
- used_[i] = true;
- --chars_left;
- break;
- }
- }
- if (used_[i]) break;
- }
- }
- return res;
- }
- private:
- static constexpr int kRadix = 26;
- array<int, kRadix> last_index_;
- vector<vector<int>> all_occurences_;
- array<bool, kRadix> used_;
- mutable int min_index_{ -1 };
- bool CanTakeAsNext(int pos) const {
- if (pos < min_index_) return false;
- for (int i = 0; i < kRadix; ++i) {
- if (!used_[i] && last_index_[i] < pos)
- return false;
- }
- min_index_ = pos;
- return true;
- }
- };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement