[Leetcode]316. Remove Duplicate Letters(C++)

题目描述

Given a string which contains only lowercase letters, remove duplicate letters so that every letter appears once and only once. You must make sure your result is the smallest in lexicographical order among all possible results.

例子

例子 1

Input: “bcabc” Output: “abc”

例子 2

Input: “cbacdcbc” Output: “acdb”

解题思路

这道题可以用贪心的思路来做，方法如下：

建立一个哈希表统计所有字母出现的次数，一个哈希表用来判断该字母是否已被使用
循环遍历原字符串：首先在哈希表中将对应字母剩余次数减一
如果当前字母已被用过，则跳过本次循环
否则，从后往前遍历结果字符串：
- 如果末尾字符串比当前候选字符大并且末尾字符串的剩余次数大于0（表示还有更优结果）则将其弹出结果字符串
  - 在哈希表中标记该末尾字符串为未使用
  - 继续遍历结果字符串
- 否则直接弹出该内层循环
将当前字符添加进结果串，并标记该字符为已使用，重复进入下一循环步骤

代码如下：

#include <string>
#include <vector>

class Solution {
public:
    std::string removeDuplicateLetters(std::string s) {
        std::vector<int> count(26, 0);
        std::vector<bool> used(26, false);
        std::string result = "";
        if (s.empty()) return result;
        for(char c: s) {
            count[c - 'a']++;
        }

        for(int i = 0; i < s.length(); i++) {
            count[s[i] - 'a']--;
            if (used[s[i] - 'a']) continue;
            // len(result) 最长不超过 26
            while (!result.empty() && s[i] < result.back() && count[result.back() - 'a'] > 0) {
                used[result.back() - 'a'] = false;
                result.pop_back();
            }
            result += s[i];
            used[s[i] - 'a'] = true;
        }

        return result;
    }
};

时间复杂度: O(n) – 因为结果字符串长度不超过26，所以内层循环次数为常数
空间复杂度: O(1)

GitHub 代码同步地址： 316.RemoveDuplicateLetters.cpp

其他题目： GitHub: Leetcode-C++-Solution 博客： Leetcode-Solutions