LeetCode 解題筆記：1081. Smallest Subsequence of Distinct Characters

作者：王一哲
日期：2026年7月19日


LeetCode 題目連結：1081. Smallest Subsequence of Distinct Characters

解題想法

中等難度題。題目給一個字串 $s$，回傳字串中最小字典序的子字串，而且子字串之中每個字母只能出現一次。這題可以用單調隊列解題，隊列中的字母依照字典序排列，遇到新的字母 c 時，從隊列最後面移除字典序大於 c 的字母。在 Python 可以用 list 或是 string 儲存隊列，在 C++ 可以用 vector 或是 string 儲存隊列。另外要記錄每個字母最後一次於 s 出現的索引值，以及隊列中目前已選的字母。

Python 程式碼

用字典儲存索引值及已選的字母，用串列儲存隊列。Runtime: 3 ms, beats 38.55%. Memory: 19.24 MB, beats 75.23%.

class Solution:
    def smallestSubsequence(self, s: str) -> str:
        # 記錄 s 之中每個字母最後一次出現的索引值
        lastIdx = {chr(i + ord('a')): -1 for i in range(26)}
        for i, c in enumerate(s):
            lastIdx[c] = i
        # 單調隊列，t 之中的字母按照字典序排列，used 記錄 t 之中是否有字母 c
        t = []
        used = {chr(i + ord('a')): False for i in range(26)}
        for i, c in enumerate(s):
            if used[c]: continue  # 已有字母 c，跳過
            # 如果 t 有資料，c 小於 t 最後一項，而且 i 小於 t[-1] 最後一次出現的索引值
            # 後面還有與 t[-1] 相同的字母可以加入，先移除
            while t and c < t[-1] and i < lastIdx[t[-1]]:
                used[t.pop()] = False  # 移除 t[-1] 並重設 used
            # c 加入 t 最後面
            t.append(c)
            used[c] = True
        # 接成字串並回傳
        return "".join(t)

用串列儲存索引值、已選的字母及隊列。Runtime: 3 ms, beats 38.55%. Memory: 19.55 MB, beats 75.23%.

class Solution:
    def smallestSubsequence(self, s: str) -> str:
        # 記錄 s 之中每個字母最後一次出現的索引值
        lastIdx = [-1] * 26
        for i, c in enumerate(s):
            lastIdx[ord(c) - ord('a')] = i
        # 單調隊列，t 之中的字母按照字典序排列，used 記錄 t 之中是否有字母 c
        t = []
        used = [False] * 26
        for i, c in enumerate(s):
            if used[ord(c) - ord('a')]: continue  # 已有字母 c，跳過
            # 如果 t 有資料，c 小於 t 最後一項，而且 i 小於 t[-1] 最後一次出現的索引值
            # 後面還有與 t[-1] 相同的字母可以加入，先移除
            while t and c < t[-1] and i < lastIdx[ord(t[-1]) - ord('a')]:
                used[ord(t.pop()) - ord('a')] = False  # 移除 t[-1] 並重設 used
            # c 加入 t 最後面
            t.append(c)
            used[ord(c) - ord('a')] = True
        # 接成字串並回傳
        return "".join(t)

用串列儲存索引值、已選的字母，用字串儲存隊列。Runtime: 3 ms, beats 38.55%. Memory: 19.36 MB, beats 39.11%.

class Solution:
    def smallestSubsequence(self, s: str) -> str:
        # 記錄 s 之中每個字母最後一次出現的索引值
        lastIdx = [-1] * 26
        for i, c in enumerate(s):
            lastIdx[ord(c) - ord('a')] = i
        # 單調隊列，t 之中的字母按照字典序排列，used 記錄 t 之中是否有字母 c
        t = ""
        used = [False] * 26
        for i, c in enumerate(s):
            if used[ord(c) - ord('a')]: continue  # 已有字母 c，跳過
            # 如果 t 有資料，c 小於 t 最後一項，而且 i 小於 t[-1] 最後一次出現的索引值
            # 後面還有與 t[-1] 相同的字母可以加入，先移除
            while t and c < t[-1] and i < lastIdx[ord(t[-1]) - ord('a')]:
                used[ord(t[-1]) - ord('a')] = False  # 移除 t[-1] 並重設 used
                t = t[:-1]
            # c 加入 t 最後面
            t += c
            used[ord(c) - ord('a')] = True
        # 回傳 t
        return t

C++ 程式碼

用 vector 儲存索引值、已選的字母，用字串儲存隊列。Runtime: 0 ms, beats 100.00%. Memory: 8.74 MB, beats 57.91%.

class Solution {
public:
    string smallestSubsequence(string s) {
        // 記錄 s 之中每個字母最後一次出現的索引值
        int n = (int)s.size();
        vector<int> lastIdx (26, -1);
        for(int i = 0; i < n; i++) {
            lastIdx[s[i] - 'a'] = i;
        }
        // 單調隊列，t 之中的字母按照字典序排列，used 記錄 t 之中是否有字母 c
        string t;
        vector<bool> used (26, false);
        for(int i = 0; i < n; i++) {
            if (used[s[i] - 'a']) continue;  // 已有字母 s[i]，跳過
            // 如果 t 有資料，s[i] 小於 t 最後一項，而且 i 小於 t.back() 最後一次出現的索引值
            // 後面還有與 t.back() 相同的字母可以加入，先移除
            while(!t.empty() && s[i] < t.back() && i < lastIdx[t.back() - 'a']) {
                used[t.back() - 'a'] = false;  // 重設 used
                t.pop_back();  // 移除 t.back()
            }
            // s[i] 加入 t 最後面
            t += s[i];
            used[s[i] - 'a'] = true;
        }
        // 回傳 t
        return t;
    }
};

用 map 儲存索引值、已選的字母，用字串儲存隊列。Runtime: 3 ms, beats 9.35%. Memory: 9.02 MB, beats 9.27%.

class Solution {
public:
    string smallestSubsequence(string s) {
        // 記錄 s 之中每個字母最後一次出現的索引值，used 記錄 t 之中是否有字母 c
        map<char, int> lastIdx;
        map<char, bool> used;
        for(int i = 0; i < 26; i++) {
            lastIdx[char(i + 'a')] = -1;
            used[char(i + 'a')] = false;
        }
        int n = (int)s.size();
        for(int i = 0; i < n; i++) {
            lastIdx[s[i]] = i;
        }
        // 單調隊列，t 之中的字母按照字典序排列
        string t;
        for(int i = 0; i < n; i++) {
            if (used[s[i]]) continue;  // 已有字母 s[i]，跳過
            // 如果 t 有資料，s[i] 小於 t 最後一項，而且 i 小於 t.back() 最後一次出現的索引值
            // 後面還有與 t.back() 相同的字母可以加入，先移除
            while(!t.empty() && s[i] < t.back() && i < lastIdx[t.back()]) {
                used[t.back()] = false;  // 重設 used
                t.pop_back();  // 移除 t.back()
            }
            // s[i] 加入 t 最後面
            t += s[i];
            used[s[i]] = true;
        }
        // 回傳 t
        return t;
    }
};

用 unordered_map 儲存索引值、已選的字母，用字串儲存隊列。Runtime: 0 ms, beats 100.00%. Memory: 8.92 MB, beats 17.14%.

class Solution {
public:
    string smallestSubsequence(string s) {
        // 記錄 s 之中每個字母最後一次出現的索引值，used 記錄 t 之中是否有字母 c
        unordered_map<char, int> lastIdx;
        unordered_map<char, bool> used;
        for(int i = 0; i < 26; i++) {
            lastIdx[char(i + 'a')] = -1;
            used[char(i + 'a')] = false;
        }
        int n = (int)s.size();
        for(int i = 0; i < n; i++) {
            lastIdx[s[i]] = i;
        }
        // 單調隊列，t 之中的字母按照字典序排列，
        string t;
        for(int i = 0; i < n; i++) {
            if (used[s[i]]) continue;  // 已有字母 s[i]，跳過
            // 如果 t 有資料，s[i] 小於 t 最後一項，而且 i 小於 t.back() 最後一次出現的索引值
            // 後面還有與 t.back() 相同的字母可以加入，先移除
            while(!t.empty() && s[i] < t.back() && i < lastIdx[t.back()]) {
                used[t.back()] = false;  // 重設 used
                t.pop_back();  // 移除 t.back()
            }
            // s[i] 加入 t 最後面
            t += s[i];
            used[s[i]] = true;
        }
        // 回傳 t
        return t;
    }
};