Smallest Subsequence of Distinct Characters: Subsequence Nhỏ Nhất Lexicographically Chứa Tất Cả Ký Tự Riêng Biệt

Đề bài: Cho string text. Tìm subsequence lexicographically nhỏ nhất chứa tất cả ký tự distinct của text đúng 1 lần.

Ví dụ: "cdadabcc" → "adbc".

Ý tưởng: Monotonic Stack + Last Occurrence

Duyệt trái → phải, maintain stack tăng dần (lexicographically). Khi thấy char c:

Nếu c đã trong stack → bỏ qua.
Nếu c < stack.top VÀ stack.top xuất hiện sau nữa (last_occurrence[stack.top] > i) → pop stack.top (sẽ thêm sau).
Push c vào stack.

Code Python


class Solution:
    def smallestSubsequence(self, text: str) -> str:
        last_occ = {c: i for i, c in enumerate(text)}
        stack = []
        in_stack = set()
        
        for i, c in enumerate(text):
            if c in in_stack:
                continue
            # Pop larger chars that appear later
            while stack and c < stack[-1] and last_occ[stack[-1]] > i:
                in_stack.remove(stack.pop())
            stack.append(c)
            in_stack.add(c)
        
        return ''.join(stack)

# Test
ob = Solution()
print(ob.smallestSubsequence("cdadabcc"))  # "adbc"
print(ob.smallestSubsequence("bcabc"))     # "abc"
print(ob.smallestSubsequence("cbacdcbc"))  # "acdb"

Giải thích test `"cdadabcc"`

i=0 'c': stack=[c]
i=1 'd': stack=[c,d]
i=2 'a': a2 → pop d; a2 → pop c; stack=[a]
i=3 'd': stack=[a,d]
i=4 'a': already in stack, skip
i=5 'b': b5 → pop d; stack=[a,b]
i=6 'c': stack=[a,b,c]
i=7 'c': skip
Result: "adbc"

Phân tích

Time: O(n) - mỗi char push/pop tối đa 1 lần.
Space: O(Σ) (Σ = alphabet size, ≤ 26 cho lowercase).
Monotonic stack pattern: maintain increasing order, pop khi có cơ hội tốt hơn sau.

Kết luận