Pythonで解く「DI文字列マッチ」問題 ― 条件を満たす順列の求め方

問題の概要

「I」（増加：Increase）と「D」（減少：Decrease）のみで構成された文字列 S が与えられます。S の長さを N とするとき、[0, 1, ..., N] の順列 A のうち、すべての i（0 ≤ i ≤ N−1）について次の条件を満たすものを任意に 1 つ返してください。

• S[i] が「I」の場合：A[i] < A[i+1]
• S[i] が「D」の場合：A[i] > A[i+1]

たとえば、入力が "IDID" の場合、出力は [0, 4, 1, 3, 2] となります。

解法のアプローチ

この問題は貪欲法（グリーディ法）を使うことでシンプルに解けます。手順は以下の通りです。

1. 0 から N までの連続した整数を要素とするリスト A を作成します（N は文字列 S の長さ）。
2. 結果を格納する空のリスト res を用意します。
3. 文字列 S の各文字 j に対して、次の処理を繰り返します。
   • j が「I」のとき：A の先頭（現時点で最小の値）を取り除き、res に追加します。
   • j が「D」のとき：A の末尾（現時点で最大の値）を取り除き、res に追加します。
4. ループ終了後、A に残った最後の 1 要素を res に追加して返します。

なぜこの方法が正しく機能するのか

「増加（I）」が要求された場面で現時点の最小値を選べば、その後にどの数を使っても必ずそれより大きくなります。逆に「減少（D）」が要求された場面で最大値を選べば、残りのどの数よりも確実に大きくなります。毎回最小値か最大値を使い切ることで、以降の制約が必ず満たされるという仕組みです。

実装例

class Solution:
    def diStringMatch(self, S):
        A = [i for i in range(len(S) + 1)]
        return [A.pop((j == 'I') - 1) for j in S] + A

ob = Solution()
print(ob.diStringMatch("IDID"))

このコードのポイントは A.pop((j == 'I') - 1) の部分です。Python では True は 1、False は 0 として扱われるため、次のような動作になります。

• j が「I」のとき：(1 − 1) = 0 番目 → リストの先頭を取り出す
• j が「D」のとき：(0 − 1) = −1 番目 → リストの末尾を取り出す

つまり、わずか 1 行で貪欲法のロジックを表現しており、最後の + A で残った 1 要素を結果に結合しています。

入力

"IDID"

出力

[0, 4, 1, 3, 2]

計算量

• 時間計算量：O(N) ― 文字列を一度走査するだけで完了します。
• 空間計算量：O(N) ― 結果のリストを保持するために必要です。

補足：Python のリストで先頭要素を削除する pop(0) は O(N) のコストがかかるため、非常に大きな入力を扱う場合は collections.deque を使うとさらに効率的になります。