C++で重複する文字を削除する

これを解決するには、次の手順に従います-

• ans：=1つの空の文字列

• 1つのスタックstを定義する

• サイズ26のアレイonStackを定義する

• 1つのマップを定義するm

• n：=sのサイズ

• iを初期化する場合：=0、i

  • m[s[i]]を1増やします

• iを初期化する場合：=0、i

  • サイズiの配列x=sを定義します

  • m[x]を1だけ減らす

  • onStack [x-'a']がゼロ以外の場合、

    • 次の反復にスキップし、次の部分を無視します

  • stが空ではなく、x を実行します。

    • onStack [top of st-'a']：=false

    • stからアイテムを削除

  • xをstに挿入

  • onStack [x-'a']：=true

• （stが空）がfalseの場合、-

  を実行します。

  • x：=stの最上位要素

  • stからアイテムを削除

  • ans =ans + x

• 配列を逆にするrev

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