Smallest Subsequence of Distinct Characters: หา Subsequence เล็กที่สุด Lexicographically

โจทย์

กำหนด string text หา Lexicographically Smallest Subsequence ที่มี ตัวอักษร distinct ครบทุกตัว ที่ปรากฏใน text อย่างละ 1 ครั้ง

ตัวอย่าง: "cdadabcc" → "adbc"

Distinct chars: a,b,c,d → ต้องมีทั้ง 4 ตัว ลำดับ lexicographically smallest

อัลกอริทึม: Monotonic Stack + Greedy

คล้าย Remove Duplicate Letters (LeetCode 316)

1. นับ last_occurrence[char] = index สุดท้ายของแต่ละ char
2. ใช้ Stack เก็บผลลัพธ์, Set in_stack ตรวจสอบว่าอยู่ใน stack แล้ว
3. Iterate ทุก char c ใน string:
   • ถ้า c in in_stack: skip (มีแล้ว)
   • While stack not empty และ c < stack[-1] และ last_occurrence[stack[-1]] > i (top ยังเจออีกในอนาคต):
     • Pop top ออกจาก stack และ in_stack
   • Push c เข้า stack, เพิ่มใน in_stack
4. Join stack เป็น string

การติดตั้ง (Python Implementation)

class Solution:
    def smallestSubsequence(self, text: str) -> str:
        last_occurrence = {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_occurrence[stack[-1]] > i:
                removed = stack.pop()
                in_stack.remove(removed)
            
            stack.append(c)
            in_stack.add(c)
        
        return ''.join(stack)

# ทดสอบ
ob = Solution()
print(ob.smallestSubsequence("cdadabcc"))      # "adbc"
print(ob.smallestSubsequence("bcabc"))         # "abc"
print(ob.smallestSubsequence("cbacdcbc"))      # "acdb"
print(ob.smallestSubsequence("abcd"))          # "abcd"

Output

adbc
abc
acdb
abcd

การทำงานทีละขั้น (text = "cdadabcc")

last_occurrence: c:7, d:2, a:3, b:4

i=0, c='c': stack=[c], in={c}
i=1, c='d': d>c, stack=[c,d], in={c,d}
i=2, c='a': a2 → no pop d; a2 → pop c
           stack=[d], in={d}; push a → stack=[d,a], in={d,a}
i=3, c='d': d in in_stack → skip
i=4, c='a': a in in_stack → skip
i=5, c='b': b5 → no pop a; b5 → no pop d
           push b → stack=[d,a,b], in={d,a,b}
i=6, c='c': c>b, push → stack=[d,a,b,c]
i=7, c='c': skip

Result: "dabc" → แต่ตัวอย่างให้ "adbc"?

แก้ไข: ตัวอย่าง output "adbc" แต่ algorithm ให้ "dabc" → ต้องตรวจสอบ logic

จริงๆ แล้ว "adbc" < "dabc" lexicographically ดังนั้น algorithm ควรให้ "adbc"

ปัญหา: ตอน i=2 (c='a'), stack=[c,d], last[d]=2 (ไม่ > i=2) ดังนั้นไม่ pop d แต่ควร pop d ได้เพราะ d ยังมีอีก (index 3? ไม่ index 3 คือ 'a') → last[d]=2 คือ index 2 เอง (d ตัวสุดท้าย)

รอ แล้ว "cdadabcc" indices: 0:c, 1:d, 2:a, 3:d, 4:a, 5:b, 6:c, 7:c last: c:7, d:3, a:4, b:5

ลองใหม่: i=0, c='c': stack=[c] i=1, c='d': stack=[c,d] i=2, c='a': a2 → pop d; a2 → pop c; push a → [a] i=3, c='d': push → [a,d] i=4, c='a': skip i=5, c='b': b5 → no pop d; b>a → push → [a,d,b] i=6, c='c': push → [a,d,b,c] i=7, c='c': skip Result: "adbc" ✓

Complexity

• Time: O(n) - แต่ละ char push/pop สูงสุด 1 ครั้ง
• Space: O(σ) - σ = alphabet size (26 สำหรับ lowercase)

สรุป

Smallest Subsequence of Distinct Characters ใช้ Monotonic Stack + Last Occurrence tracking Greedy: พยายามวาง char น้อยที่สุดไว้หน้าสุด โดย pop char ใหญ่กว่าที่ยังเจอได้ในอนาคต

หากมีข้อสงสัย สามารถถามได้ในส่วนความคิดเห็นครับ