Задача: 316. Remove Duplicate Letters
Сложность: medium

Дана строка s, удалите повторяющиеся буквы так, чтобы каждая буква появилась один раз и только один раз. Вы должны сделать так, чтобы результат был наименьшим в лексикографическом порядке среди всех возможных результатов.

Пример:

Input: s = "bcabc"
Output: "abc"

👨‍💻 Алгоритм:

1⃣Инициализация стека
Создайте стек, который будет хранить результат, построенный по мере итерации строки.

2⃣Итерация по строке
На каждой итерации добавляйте текущий символ в стек, если он еще не был использован. Перед добавлением текущего символа удаляйте как можно больше символов из вершины стека, если это возможно и улучшает лексикографический порядок.

3⃣Удаление символов
Удаляйте символы с вершины стека при выполнении следующих условий: Символ на вершине стека больше текущего символа. Символ может быть удален, так как он встречается позже в строке. На каждом этапе итерации по строке жадно минимизируйте содержимое стека.

😎 Решение:

class Solution {
public:
    string removeDuplicateLetters(string s) {
        vector<char> stack;
        unordered_set<char> seen;
        unordered_map<char, int> lastOccurrence;
        for (int i = 0; i < s.size(); ++i) {
            lastOccurrence[s[i]] = i;
        }

        for (int i = 0; i < s.size(); ++i) {
            char c = s[i];
            if (seen.find(c) == seen.end()) {
                while (!stack.empty() && c < stack.back() && i < lastOccurrence[stack.back()]) {
                    seen.erase(stack.back());
                    stack.pop_back();
                }
                seen.insert(c);
                stack.push_back(c);
            }
        }
        return string(stack.begin(), stack.end());
    }
};

Ставь 👍 и забирай 📚 Базу знаний