Pythonで文字列をk個ごとのパーティションに分割し重複文字を除去する方法

問題の概要

文字列 s と整数値 k が与えられます。ここで、k は文字列 s の長さ n の約数であるとします。このとき、s をサイズ k の部分文字列 t_i に n/k 個に分割できます。さらに、これらの t_i を使って、次の条件を満たす文字列 u_i を作成します。

• u_i を構成する文字は、t_i に含まれる文字の部分列であること
• u_i 内では同じ文字が繰り返し現れないようにする（各文字の出現頻度を 1 回にする）

私たちの目的は、これらの文字列 u_i をすべて求めることです。

入力例

たとえば、s = "MMPQMMMRM"、k = 3 が与えられた場合、出力は ["MP", "QM", "MR"] になります。これは、s の長さが 9 で k が 3 なので、9 ÷ 3 = 3 個の部分文字列「MMP」「QMM」「MRM」に分割されるためです。しかし、重複する文字は許されないため、それぞれ重複を除去すると「MP」「QM」「MR」となります。

解法のアプローチ

この問題を解くには、次の手順に従います。

• i := 0
• ret := 新しいリスト
• mp := 新しいマップ（辞書）
• to_print := 空文字列
• i が s のサイズ未満である間、以下を繰り返す：
  • i mod k が 0 かつ i が 0 でない場合：
    • ret の末尾に to_print を追加する
    • mp と to_print をクリアする
  • s[i] が mp に存在しない場合：
    • mp[s[i]] := 0
    • to_print := to_print + s[i]
  • i := i + 1
• ループ終了後、ret の末尾に to_print を追加する
• ret を返す

実装例

以下の Python 実装を見ると、理解が深まるでしょう。

def solve(s, k):
   i = 0
   ret = []
   mp, to_print = {}, ""
   while i < len(s):
      if i % k == 0 and i != 0:
         ret.append(to_print)
         mp, to_print = {}, ""
      if s[i] not in mp.keys():
         mp[s[i]] = 0
         to_print += s[i]
      i += 1
   ret.append(to_print)
   return ret

s = "MMPQMMMRM"
k = 3
print(solve(s, k))

コードの解説

このアルゴリズムでは、インデックス i を使って文字列を先頭から順に走査します。i が k の倍数になるタイミング（区切りの位置）で、それまでに構築した文字列 to_print を結果リスト ret に追加し、辞書 mp と to_print をリセットして新しいブロックの処理に備えます。各ブロック内では、まだ出現していない文字だけを to_print に追加していくため、重複文字は自動的に除去されます。最後のブロックについては、ループ終了後に改めて ret へ追加しています。

文字列全体を一度だけ走査するため、このアルゴリズムの計算量は O(n) となり、非常に効率的です。

入力

"MMPQMMMRM", 3

出力

['MP', 'QM', 'MR']