Leetcode#316-去除重复字母

题目描述

给你一个字符串 s ，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证返回结果的字典序最小（要求不能打乱其他字符的相对位置）。

示例 1：

输入：s = "bcabc"
输出："abc"

示例 2：

输入：s = "cbacdcbc"
输出："acdb"

提示：
1 <= s.length <= 104
s 由小写英文字母组成

解题思路

思路与官方题解类似，描述见官方题解。

源码

class Solution {
public:
    string removeDuplicateLetters(string s) {
        vector<int> cnt(26,0);
        vector<bool> inStack(26,false);
        int n=s.length();
        string ans;
        for(char c:s)
        {
            cnt[c-'a']++;
        }
        for(int i=0;i<n;i++)
        {
            if(!inStack[s[i]-'a'])
            {
                while(!ans.empty()&&s[i]<ans.back())
                {
                    char temp=ans.back();
                    if(cnt[temp-'a']>1)
                    {
                        cnt[temp-'a']--;
                        inStack[temp-'a']=false;
                        ans.pop_back();
                    }
                    else
                    {
                        break;
                    }
                }
                ans.push_back(s[i]);
                inStack[s[i]-'a']=true;
            }
            else
            {
                cnt[s[i]-'a']--;
            }
        }
        return ans;
    }
};

题目来源

来源：力扣（LeetCode）