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

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

Пример:

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

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

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

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

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

😎 Решение:

class Solution {
    func removeDuplicateLetters(_ s: String) -> String {
        var stack = [Character]()
        var seen = Set<Character>()
        let lastOccurrence = Dictionary(uniqueKeysWithValues: s.enumerated().map { ($1, $0) })

        for (i, c) in s.enumerated() {
            if !seen.contains(c) {
                while let last = stack.last, c < last, i < lastOccurrence[last]! {
                    seen.remove(stack.popLast()!)
                }
                seen.insert(c)
                stack.append(c)
            }
        }
        return String(stack)
    }
}

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