LeetCode 1081. 不同字符的最小子序列

题目描述

返回字符串 text 中按字典序排列最小的子序列，该子序列包含 text 中所有不同字符一次。
示例 1：

输入："cdadabcc"
输出："adbc"

题目解析

1. 详细描述一下题目，要求是字符串中所有字母均要出现，且只出现一次，且返回字典序最小的子序列。
2. 构建栈维护最终结构，构建贪心策略，当栈顶元素比处理字符大时，且后续字母还包含栈顶元素时，进行栈中淘汰，同时记录处理字符状态，若栈中已包含了该字符，则不处理该字符。

C++代码

class Solution {
public:
    string smallestSubsequence(string text) {
        stack<int> ansStack;
        int nums[26];
        memset(nums, 0, sizeof(nums));
        for(int i = 0;i < text.size(); i++) {
            nums[text[i] - 'a']++;
        }
        
        int status = 0;
        for(int i = 0; i < text.size(); i++) {      
            if((status & (1 << (text[i] - 'a'))) == 0)  {
                while(ansStack.size() > 0 && ansStack.top() >= text[i] - 'a' && nums[ansStack.top()] > 0) {
                    status ^= (1 << ansStack.top());
                    ansStack.pop();
                }
                ansStack.push(text[i] - 'a');
                status |= (1 << ansStack.top());    
            }
            nums[text[i] - 'a']--;
        }

        string ans(ansStack.size(), 'a');
        int idx = ansStack.size();
        while(ansStack.size()) {
            ans[--idx] = ansStack.top() + 'a';
            ansStack.pop();
        }
        return ans;
    }
};