Loại bỏ các chữ cái trùng lặp trong C ++

Giả sử chúng ta có một chuỗi chỉ gồm các chữ cái thường. Chúng tôi phải loại bỏ tất cả các chữ cái trùng lặp để tất cả các chữ cái chỉ xuất hiện một lần. Và chúng ta phải hiển thị kết quả theo trình tự từ vựng nhỏ nhất. Vì vậy, nếu đầu vào là “abccb”, thì kết quả sẽ là “abc”

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• ans:=một chuỗi trống

• Xác định một ngăn xếp

• Xác định một mảng onStack có kích thước 26

• Xác định một bản đồ m

• n:=kích thước của s

• để khởi tạo i:=0, khi i

  • tăng m [s [i]] lên 1

• để khởi tạo i:=0, khi i

  • Xác định một mảng x =s có kích thước i

  • giảm dần m [x] xuống 1

  • nếu onStack [x - 'a'] khác 0 thì

    • Bỏ qua bước lặp tiếp theo, bỏ qua phần sau

  • trong khi st không trống và x

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

    • xóa mục khỏi st

  • chèn x vào st

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

• while (st trống) là false, do -

  • x:=phần tử hàng đầu của st

  • xóa mục khỏi st

  • ans =ans + x

• đảo ngược vòng xoay mảng

• trả lại ans

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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"));
}

Đầu vào

“abccb”

Đầu ra

“abc”