【Python】部分文字列のソート操作で文字列sをtに変換できるか判定する方法

問題の概要

2つの数字のみで構成された文字列 s と t が与えられます。次の操作を何度でも繰り返し適用して、文字列 s を文字列 t に変換できるかどうかを判定するプログラムを作成します。

操作の定義： s の中から空でない部分文字列を1つ選び、その範囲内の文字を昇順（小さい順）に並べ替えます。

例として、s = "95643"、t = "45963" の場合、出力は True になります。実際に次のような手順で変換できるためです。

"95643" → "95463" → "45963"

解法のアプローチ

この問題は、以下の手順で解くことができます。

• 各数字（0〜9）ごとに、その数字が s 内に出現する位置インデックスを記録するマップ places を用意します。デフォルト値はリスト型です。

• s の末尾から先頭に向かってインデックス i を走査し、key := int(s[i]) として、i を places[key] の末尾に追加します。これにより、各数字の出現位置は「左側にあるものほどリストの後ろ」に格納されます。

• t の各文字 e に対して、以下の処理を繰り返します。

  • key := int(e) とします。

  • places[key] が空であれば False を返します（s にもうその数字が残っていないため変換不可能です）。

  • i := places[key] の末尾の要素、つまり残っている中で最も左側にある key の位置とします。

  • j を 0 から key - 1 まで走査し、places[j] が空でなく、その末尾の要素（最も左側にある j の位置）が i より小さい場合は False を返します。これは「key より小さい数字が key の左側にまだ残っている」状態であり、key を目的の位置まで移動させる妨げになるためです。

  • places[key] の末尾の要素を削除して、その数字を使用済みにします。

• すべての文字を処理し終えたら True を返します。

なぜこのアルゴリズムが正しく動くのか

部分文字列を昇順にソートするという操作では、ある数字は同じ部分文字列に含まれるより大きい数字を飛び越えて左へ移動できますが、より小さい数字の右側へ移動することは決してできません。ソートを行うと小さい数字が必ず左側に配置されるためです。

そこで、t を左から右へ1文字ずつ構築していくことを考えます。t の現在の文字が数字 k であるとき、s に残っている k のうち最も左側にあるものを使うのが最適です。ただし、その位置よりも左に未使用の k 未満の数字が存在する場合、k はそれらの小さい数字を追い越すことができないため変換は不可能となり、False を返します。逆に、そのような障害となる数字がなければ、k は左側の大きな数字たちを越えて必ず目的の位置へ移動できます。

Pythonでの実装例

それでは、理解を深めるために以下の実装を見てみましょう。

from collections import defaultdict


def solve(s, t):
   places = defaultdict(list)
   for i in reversed(range(len(s))):
      key = int(s[i])
      places[key].append(i)

   for e in t:
      key = int(e)
      if not places[key]:
         return False
      i = places[key][-1]
      for j in range(key):
         if places[j] and places[j][-1] < i:
            return False
      places[key].pop()
   return True


s = "95643"
t = "45963"
print(solve(s, t))

入力

"95643", "45963"

出力

True

計算量

時間計算量は O(n × 10) = O(n)、空間計算量は O(n) です。ここで n は文字列の長さを表します。内側のループは数字 0〜8 のチェックのみで最大9回しか繰り返されないため、全体として文字列の長さに対して線形時間で効率的に処理できます。