สมมติว่าเรามีสตริงที่ประกอบด้วยตัวพิมพ์เล็กเท่านั้น เราต้องลบตัวอักษรที่ซ้ำกันทั้งหมดเพื่อให้ตัวอักษรทั้งหมดเกิดขึ้นเพียงครั้งเดียว และเราต้องแสดงผลในลำดับพจนานุกรมที่เล็กที่สุด ดังนั้นหากอินพุตเป็นเหมือน “abccb” ผลลัพธ์จะเป็น “abc”
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
ans :=หนึ่งสตริงว่าง
-
กำหนดหนึ่งสแต็ก st
-
กำหนดอาร์เรย์ onStack ขนาด 26
-
กำหนดหนึ่งแผนที่ m
-
n :=ขนาดของ s
-
สำหรับการเริ่มต้น i :=0 เมื่อฉัน
-
เพิ่ม m[s[i]] ขึ้น 1
-
-
สำหรับการเริ่มต้น i :=0 เมื่อฉัน
-
กำหนดอาร์เรย์ x =s ขนาด i
-
ลด m[x] โดย 1
-
ถ้า onStack[x - 'a'] ไม่ใช่ศูนย์ ดังนั้น
-
ข้ามไปยังการวนซ้ำถัดไป ละเว้นส่วนต่อไปนี้
-
-
ในขณะที่ st ไม่ว่างเปล่าและ x
-
onStack[top of st - 'a'] :=false
-
ลบรายการออกจาก st
-
-
ใส่ x ลงใน st
-
onStack[x - 'a'] :=จริง
-
-
ในขณะที่ (st ว่างเปล่า) เป็นเท็จ ทำ -
-
x :=องค์ประกอบด้านบนของ st
-
ลบรายการออกจาก st
-
ans =ans + x
-
-
ย้อนกลับรอบอาร์เรย์
-
กลับมาอีกครั้ง
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> 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);
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'] = false;
st.pop();
}
st.push(x);
onStack[x - 'a'] = true;
}
while(!st.empty()){
char x = st.top();
st.pop();
ans += x;
}
reverse(ans.begin(), ans.end());
return ans;
}
};
main(){
Solution ob;
cout << (ob.removeDuplicateLetters("abccb"));
} อินพุต
“abccb”
ผลลัพธ์
“abc”
