ลบตัวอักษรซ้ำให้เรียงเล็กซิโครกราฟิกใน C++

ภาพรวมปัญหา

ลบตัวอักษรซ้ำในสตริง ให้เหลือแต่ละตัว 1 ตัว และเรียงตามลำดับเล็กซิโครกราฟิกที่น้อยที่สุด

ตัวอย่าง

"abccb" → "abc"

วิธีแก้ปัญหา: Monotonic Stack + Greedy

1. นับความถี่แต่ละตัวอักษร
2. วนอ่านตัวอักษร: ลด frequency, ถ้าอยู่ใน stack แล้ว skip
3. ขณะ stack ไม่ว่าง และ ตัวปัจจุบัน < stack.top() และตัวบน stack ยังมีเหลืออยู่ → pop
4. push ตัวปัจจุบันเข้า stack
5. ท้ายสุด reverse stack ได้คำตอบ

โค้ด C++

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

class Solution {
public:
    string removeDuplicateLetters(string s) {
        string ans = "";
        stack<char> st;
        vector<int> onStack(26, 0);
        map<char, int> m;
        for (char c : s) m[c]++;
        for (char c : s) {
            m[c]--;
            if (onStack[c - 'a']) continue;
            while (!st.empty() && c < st.top() && m[st.top()]) {
                onStack[st.top() - 'a'] = 0;
                st.pop();
            }
            st.push(c);
            onStack[c - 'a'] = 1;
        }
        while (!st.empty()) { ans += st.top(); st.pop(); }
        reverse(ans.begin(), ans.end());
        return ans;
    }
};

int main() {
    Solution ob;
    cout << (ob.removeDuplicateLetters("abccb"));
}

ผลลัพธ์

"abc"

การวิเคราะห์ความซับซ้อน

• เวลา: O(n) — n = ความยาวสตริง
• พื้นที่: O(1) — stack และ array ขนาดคงที่ 26