Pythonで辞書順最小の部分列を求める：すべての異なる文字を1回ずつ含む方法

文字列 text が与えられたとき、そこに含まれるすべての異なる文字をそれぞれちょうど1回だけ使用する「辞書順最小の部分列」を求めることを考えます。たとえば、入力が "cdadabcc" の場合、答えは "adbc" となります。

解き方のアプローチ

この問題はスタックと貪欲法（グリーディ法）を組み合わせることで効率的に解けます。ポイントは「スタックの先頭にある文字より小さい文字が出現し、その先頭の文字が文字列の後方にまだ残っているなら、先頭の文字を取り除いてもよい」という発想です。具体的な手順は以下の通りです。

• スタック st、マップ last_o（各文字が最後に出現するインデックス）、considered（各文字がすでに採用済みかどうか）を空の状態で用意します。
• i を「テキストの長さ − 1」から 0 まで逆順に走査します。
  • text[i] が last_o に存在しない場合：
    • last_o[text[i]] := i
    • considered[text[i]] := false
• i := 0 とし、i がテキストの長さに達するまで以下を繰り返します。
  • スタックが空の場合：text[i] をスタックにプッシュし、considered[text[i]] := true、i を 1 増やします。
  • スタックの先頭 > text[i] かつ considered[text[i]] == false の場合：
    • last_o[スタックの先頭] > i であれば、先頭の文字は後で再び使えるため、considered[先頭の文字] := false としてスタックからポップします。
    • そうでなければ、considered[text[i]] := true として text[i] をスタックに挿入し、i を 1 増やします。
  • スタックの先頭 < text[i] かつ considered[text[i]] == false の場合：text[i] をスタックに挿入し、considered[text[i]] := true、i を 1 増やします。
  • いずれの条件にも当てはまらない場合：単に i を 1 増やします。
• 最後に、スタックに残った文字を順に連結した文字列を返します。

それでは、実際の実装を見ながら理解を深めましょう。

実装例

class Solution(object):
    def smallestSubsequence(self, text):
        """
        :type text: str
        :rtype: str
        """
        stack = []
        last_o = {}
        considered = {}
        for i in range(len(text)-1, -1, -1):
            if text[i] not in last_o:
                last_o[text[i]] = i
                considered[text[i]] = False
        i = 0
        while i < len(text):
            if len(stack) == 0:
                stack.append(text[i])
                considered[text[i]] = True
                i += 1
            elif stack[-1] > text[i] and considered[text[i]] == False:
                if last_o[stack[-1]] > i:
                    considered[stack[-1]] = False
                    stack.pop()
                else:
                    considered[text[i]] = True
                    stack.append(text[i])
                    i += 1
            elif stack[-1] < text[i] and considered[text[i]] == False:
                stack.append(text[i])
                considered[text[i]] = True
                i += 1
            else:
                i += 1
        return "".join(i for i in stack)

入力

"cdadabcc"

出力

"adbc"

動作のポイント

入力 "cdadabcc" を処理すると、スタックの状態は [c] → [c, d] → [a] → [a, d] → [a, d, b] → [a, d, b, c] と変化していきます。途中で「後ろに同じ文字が残っている先頭の文字」が取り除かれることで、すべての異なる文字 {a, b, c, d} を1回ずつ含む辞書順最小の部分列 "adbc" が得られます。

なお、各文字のプッシュとポップはそれぞれ高々1回しか行われないため、時間計算量は O(n)、必要な追加メモリも O(n) です（n は文字列の長さ）。このことから、本手法は非常に効率的であると言えます。