Skip to content

LeetCode: 316-Remove Duplicate Letters 解題紀錄

Last Updated on 2022-03-18 by Clay

題目

Given a string s, 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.

Example 1:

Input: s = "bcabc"
Output: "abc"

Example 2:

Input: s = "cbacdcbc"
Output: "acdb"

Constraints:

  • 1 <= s.length <= 104
  • s consists of lowercase English letters.

Note: This question is the same as 1081: https://leetcode.com/problems/smallest-subsequence-of-distinct-characters/

題目輸入一組字串，字串中只會存在小寫英文字母。我們要做的就是刪除掉重複的字母直到該字母在字串中僅出現一次。

除此之外，我們需要保證刪除重複項字元的最終字串，是最小的字典序。

比方說 abca，雖然刪掉開頭或尾端的 a 都是不會出現重複字母的答案，但是以字典序來看，abc 比 bca 來得更小。

解題思路

Stack 容器解法

首先我先將原始字串遍歷過一遍並計算每個字母出現的次數，接著再建立 stack 的容器以及紀錄是否選擇過字母的布林陣列。

在將該字母推入容器前，會先判斷容器頂部的字母是否在字典序上小於我當前要推入容器的字母，這裡分成三種情況：

  1. 容器頂部的字母小於當前要推入的字母：判斷不需要彈出容器頂部字母，直接推入當前字母
  2. 容器頂部的字母大於當前要推入的字母，但這字母在後續字串中已經不會再出現：判斷不能彈出容器頂部字母，直接推入當前字母
  3. 容器頂部的字母大於當前要推入的字母，且該字母在後續字串中仍會出現：彈出容器頂部字母，再次將該字母設定為未選取，並繼續判斷容器的下一個頂部字母；直到容器為空或是頂部字母符合上述情況 1 & 2，這才將當前要推入的字母推入容器

遍歷結束後，將 stack 容器內的字母彈出並反轉，就成了按照字典序組成的解答字串。


複雜度

Time complexityO(n)
Space complexityO(n)


C++ 範例程式碼

class Solution {
public:
    string removeDuplicateLetters(string s) {
        // Init
        vector<bool> selected(26, false);
        vector<int> count(26, 0);
        stack<int> st;
        
        // Count
        for (auto& c: s) {
            ++count[c-'a'];
        }
        
        // Selection
        for (auto c: s) {
            --count[c-'a'];
            
            // If we had selected the current character, we can skip it
            if (selected[c-'a']) continue;
            
            // Make sure the smallest in lexicographical order
            while (!st.empty() && st.top()>c && count[st.top()-'a']>0) {
                selected[st.top()-'a'] = false;                
                st.pop();
            }
            
            st.push(c);
            selected[c-'a'] = true;            
        }
        
        // Answer
        string answer;
        while (!st.empty()) {
            answer.push_back(st.top());
            st.pop();
        }
        
        // Reverse
        reverse(answer.begin(), answer.end());
        
        return answer;
    }
};



Python 範例程式碼

class Solution:
    def removeDuplicateLetters(self, s: str) -> str:
        # Init
        selected = [False for _ in range(26)]
        count = [0 for _ in range(26)]
        st = []
        
        # Count
        for c in s:
            count[ord(c)-ord('a')] += 1
        
        # Selection
        for c in s:
            count[ord(c)-ord('a')] -= 1
            
            # If we had selected the current character, we can skip it
            if selected[ord(c)-ord('a')]: continue
            
            # Make sure the smallest in lexicographical order
            while st and ord(st[-1])>ord(c) and count[ord(st[-1])-ord('a')]>0:
                selected[ord(st[-1])-ord('a')] = False                
                st.pop()
            
            st.append(c)
            selected[ord(c)-ord('a')] = True            
        
        # Answer
        return ''.join(st)



References

Read More

Tags:

Leave a Reply