删除C ++中的重复字母
为了解决这个问题，我们将遵循以下步骤-
ans：=一个空字符串
定义一个堆栈st
在大小为26的onStack上定义一个数组
定义一张映射
n：=s的大小
用于初始化i：=0，当i<n时，将i增加1做-
将m[s[i]]增加1
用于初始化i：=0，当i<n时，将i增加1做-
onStack[st-'a'的顶部]：=false
从st删除项目
跳到下一个迭代，忽略以下部分
定义一个数组x=s，其大小为i
递减m[x]1
如果onStack[x-'a']不为零，则
当st不为空且x<st.top()时，执行-
将x插入st
onStack[x-'a']：=true
当（st为空）为false时，执行-
x：=st的顶部元素
从st删除项目
ans=ans+x
反转阵列转速
返回ans
示例
让我们看下面的实现以更好地理解-
#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”