Cho chuỗi chỉ chứa chữ cái thường. Xóa ký tự trùng lặp sao cho mỗi ký tự chỉ xuất hiện 1 lần, và kết quả có thứ tự từ điển nhỏ nhất (lexicographically smallest).
Ví dụ
"abccb" → "abc" (không phải "acb" vì abc < acb).
Thuật toán: Stack đơn điệu + Đếm tần suất
- Đếm tần suất mỗi ký tự trong
s. - Duyệt chuỗi, dùng stack xây dựng kết quả:
- Giảm tần suất ký tự hiện tại.
- Nếu ký tự đã có trong stack → bỏ qua.
- Ngược lại: trong khi stack không rỗng, ký tự đỉnh > ký tự hiện tại, VÀ ký tự đỉnh còn xuất hiện sau (tần suất > 0) → pop stack (bỏ ký tự lớn hơn để lấy ký tự nhỏ hơn trước).
- Push ký tự hiện tại vào stack, đánh dấu đã có.
- Chuyển stack thành chuỗi kết quả.
Cài đặt C++
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<string> v) {
cout << "[";
for (int i = 0; i < v.size(); i++) cout << v[i] << ", ";
cout << "]" << endl;
}
class Solution {
public:
string removeDuplicateLetters(string s) {
string ans = "";
stack<char> st;
vector<int> onStack(26, 0);
map<char, int> m;
int n = s.size();
for (int i = 0; i < n; i++) m[s[i]]++;
for (int i = 0; i < n; i++) {
char x = s[i];
m[x]--;
if (onStack[x - 'a']) continue;
while (!st.empty() && x < st.top() && m[st.top()]) {
onStack[st.top() - 'a'] = 0;
st.pop();
}
st.push(x);
onStack[x - '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");
return 0;
}
Độ phức tạp
- Thời gian:
O(n)— mỗi ký tự push/pop tối đa 1 lần. - Không gian:
O(1)— stack và mảng kích thước cố định 26.
Input / Output
Input: "abccb" Output: "abc"