Buckle practice - 24 remove repeated letters

24 Remove duplicate letters

1. Problem description
Give you a string containing only lowercase letters , Please remove the duplicate letters from the string , Make each letter appear only once . Ensure that the dictionary order of the returned results is the smallest （ The relative position of other characters should not be disturbed ）.

Example 1:

Input : “bcabc”

Output : “abc”

Example 2:

Input : “cbacdcbc”

Output : “acdb”

2. Enter description
Enter a string containing only lowercase letters
3. The output shows that
Output results . There are no extra spaces or blank lines at the beginning and end .
4. Example
Input
cbacdcbc
Output
acdb
5. Code

#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
using namespace std;

string removeDuplicateLetters(string s)
{
        // Subject requirements ：
	// Remove duplicate letters from the string , Make each letter appear only once 
	// Ensure that the dictionary order of the returned results is the smallest （ The relative position of other characters should not be disturbed ）.
	// Their thinking ：
	//1. First, sort according to the dictionary order , So greedy thoughts 
	//2. Because the relative order cannot be changed , Therefore, we need to consider the dictionary order on the premise of ensuring that each letter appears at least once 
    //3. Use monotone stack to ensure dictionary sequence （ From small to large ）, Monotonic stack ： Non increasing or non decreasing stack .
	//4. The conditions for the stack top elements to be out of the stack should be limited , Only when the stack is not empty   And   The dictionary order of the elements at the top of the stack is after the new elements currently traversed   And   When the stack top element will appear later  , Out of the stack 


	//1. Declare variables 
	vector<int>num(26, 0);// Notice the initialization method here , Statistics a~z The number of times the letter appears , The initial values are all 0
	vector<bool>exist(26, false);// Used to count whether the element exists in the stack 
	//2. Count the number of occurrences of each character 
	for (int i = 0; i < s.size(); i++)
		num[s[i] - 'a']++;
	//3. Traversal string , Perform stack in and stack out operations 
	string ans = "";// Use this simulation stack 
	for (int i = 0; i < s.size(); i++)
	{
    
		if (!exist[s[i] - 'a'])// Never existed in the stack 
		{
    
			// Focus on understanding the following code   The element at the top of the stack is ans.back()
			// Stack is not empty.  &&  The top element of the stack is at the end of the dictionary  &&  There are still remaining occurrences of the top element 
			while (ans.size()!=0  &&  ans.back()>s[i]  &&  num[ans.back()-'a']>0 )
			{
    
				exist[ans.back() - 'a'] = false;// Modify the appearance status 
				ans.pop_back();// Out of the stack 
			}

			ans.push_back(s[i]);// The letters in this position are pressed 
			exist[s[i] - 'a'] = true;// Modify the appearance status 
		}
		num[s[i]-'a']--;// Every time you traverse a letter , The number of occurrences of this letter is reduced by one 
	}
	return ans;
}


int main()
{
    
	string s;
	cin >> s;
	string res = removeDuplicateLetters(s);
	cout << res;
	return 0;
}