Pythonで各列をソート済みにするために削除すべき列の最小数を求める方法

N個の小文字のみで構成された文字列の配列Aがあるとします。すべての文字列は同じ長さです。ここで、任意の削除インデックスの集合を選び、各文字列からそのインデックス位置にある文字をすべて削除できるものとします。

例えば、配列Aが["abcdef", "uvwxyz"]で、削除インデックスが{0, 2, 3}の場合、削除後の最終的な配列は["bef", "vyz"]となり、Aの残りの列は["b","v"]、["e","y"]、["f","z"]となります。

削除インデックスの集合Dを選んだとき、削除後にAの残りの各列が非降順（昇順）にソートされている状態にしたいとします。このとき、Dの長さとしてあり得る最小値を求めるのが問題です。

入力が["cba", "daf", "ghi"]の場合、出力は1になります。これは、D = {1}を選べば、各列["c","d","g"]と["a","f","i"]が非降順にソートされるためです。一方、D = {}（何も削除しない）を選ぶと、列["b","a","h"]が非降順にならず、条件を満たせません。

解法のアプローチ

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

• A：配列から文字列を取り出し、文字ごとに異なる列へ分割した行列を作成する
• B：新しい空のリストを作成する
• A内の各列colに対して以下を繰り返す
  • colがすでにソート済みであれば、Bに0を挿入する
  • そうでなければ、Bに1を挿入する
• Bの全要素の合計を返す（これが削除が必要な列の数になる）

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

実装例

class Solution:
   def minDeletionSize(self, A):
      return sum([1-(sorted(col)==list(col)) for col in zip(*A)])
ob = Solution()
print(ob.minDeletionSize(["cba","daf","ghi"]))

このコードでは、zip(*A)を使うことで配列を転置し、各行（元々の文字列）を行方向から列方向へ変換しています。その上で、sorted(col) == list(col)によって各列がすでにソート済みかどうかを判定し、ソートが必要な列だけをカウントして合計しています。非常に簡潔でPythonらしい一行での実装となっています。

入力

["cba","daf","ghi"]

出力

1