删除C ++中的重复字母

假设我们有一个仅包含小写字母的字符串。我们必须删除所有重复的字母，以便所有字母仅出现一次。并且我们必须以最小的字典顺序显示结果。因此，如果输入像“ abccb”，那么结果将是“ abc”

为了解决这个问题，我们将遵循以下步骤-

• 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”