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

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

Пример:

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

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

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

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

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

😎 Решение:

class Solution {
    function removeDuplicateLetters($s) {
        $stack = [];
        $seen = [];
        $lastOccurrence = [];
        for ($i = 0; $i < strlen($s); $i++) {
            $lastOccurrence[$s[$i]] = $i;
        }

        for ($i = 0; $i < strlen($s); $i++) {
            $c = $s[$i];
            if (!isset($seen[$c])) {
                while (!empty($stack) && $c < end($stack) && $i < $lastOccurrence[end($stack)]) {
                    unset($seen[array_pop($stack)]);
                }
                $seen[$c] = true;
                $stack[] = $c;
            }
        }
        return implode('', $stack);
    }
}

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