316. Remove Duplicate Letters

public class Solution {
    public string RemoveDuplicateLetters(string s) {
        var stack = new Stack<char>();
        var seen = new HashSet<char>();
        var lastOccurrence = new Dictionary<char, int>();
        for (int i = 0; i < s.Length; i++) {
            lastOccurrence[s[i]] = i;
        }
        for (int i = 0; i < s.Length; i++) {
            char c = s[i];
            if (!seen.Contains(c)) {
                while (stack.Count > 0 && c < stack.Peek() && i < lastOccurrence[stack.Peek()]) {
                    seen.Remove(stack.Pop());
                }
                seen.Add(c);
                stack.Push(c);
            }
        }
        return new string(stack.Reverse().ToArray());
    }
}

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public string RemoveDuplicateLetters(string s) {
        var stack = new stack<char>();
        var seen = new HashSet<char>();
        var lastOccurrence = new unordered_map<char, int>();
        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.Contains(c)) {
                while (stack.size() > 0 && c < stack.Peek() && i < lastOccurrence[stack.Peek()]) {
                    seen.Remove(stack.pop());
                }
                seen.push_back(c);
                stack.push(c);
            }
        }
        return new string(stack.Reverse().ToArray());
    }
}

import java.util.*;

class Solution {
    public String removeDuplicateLetters(String s) {
        Stack<Character> stack = new Stack<>();
        Set<Character> seen = new HashSet<>();
        Map<Character, Integer> lastOccurrence = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            lastOccurrence.put(s.charAt(i), i);
        }

        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (!seen.contains(c)) {
                while (!stack.isEmpty() && c < stack.peek() && i < lastOccurrence.get(stack.peek())) {
                    seen.remove(stack.pop());
                }
                seen.add(c);
                stack.push(c);
            }
        }
        StringBuilder result = new StringBuilder();
        for (char c : stack) {
            result.append(c);
        }
        return result.toString();
    }
}

class Solution {
    removeDuplicateLetters(s) {
        const stack = [];
        const seen = new Set();
        const lastOccurrence = {};
        for (let i = 0; i < s.length; i++) {
            lastOccurrence[s[i]] = i;
        }

        for (let i = 0; i < s.length; i++) {
            const c = s[i];
            if (!seen.has(c)) {
                while (stack.length && c < stack[stack.length - 1] && i < lastOccurrence[stack[stack.length - 1]]) {
                    seen.delete(stack.pop());
                }
                seen.add(c);
                stack.push(c);
            }
        }
        return stack.join('');
    }
}

class Solution:
    def removeDuplicateLetters(self, s) -> str:
        stack = []
        seen = set()
        last_occurrence = {c: i for i, c in enumerate(s)}

        for i, c in enumerate(s):
            if c not in seen:
                while stack and c < stack[-1] and i < last_occurrence[stack[-1]]:
                    seen.discard(stack.pop())
                seen.add(c)
                stack.append(c)
        return ''.join(stack)

func removeDuplicateLetters(s string) string {
    stack := []rune{}
    seen := make(map[rune]bool)
    lastOccurrence := make(map[rune]int)
    for i, c := range s {
        lastOccurrence[c] = i
    }

    for i, c := range s {
        if !seen[c] {
            for len(stack) > 0 && c < stack[len(stack)-1] && i < lastOccurrence[stack[len(stack)-1]] {
                seen[stack[len(stack)-1]] = false
                stack = stack[:len(stack)-1]
            }
            seen[c] = true
            stack = append(stack, c)
        }
    }
    return string(stack)
}

Algorithm

Инициализация стека

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

Итерация по строке

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

Удаление символов

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

😎