Pythonで各文字が最大1つの部分にのみ出現するように文字列を分割し、各区画のサイズを求めるプログラム

問題の概要

小文字の英字のみで構成された文字列 s が与えられたとします。この文字列を、どの文字も複数の部分にまたがって出現しないという条件を満たすように、できるだけ多くの部分（パーティション）に分割し、それぞれの部分の長さをリストとして求めます。

たとえば、入力が s = "momoplaykae" の場合、文字列は ["momo", "p", "l", "ayka", "e"] の5つに分割できます。「m」は最初の部分に、「a」は4番目の部分にのみ含まれており、すべての文字が1つの部分に収まっているため条件を満たしています。よって出力は [4, 1, 1, 4, 1] となります。

解法のアプローチ

この問題は、各文字の残りの出現回数を管理しながら文字列を左から右へ走査することで解けます。具体的な手順は以下の通りです。

• count：文字列 s に含まれる各文字とその出現回数を記録したマップ（Counter）を作成します。
• out：結果を格納する空のリスト、stk：未完了の文字を管理する空のスタックを用意します。
• length：現在処理中の部分の長さを表すカウンターを 0 で初期化します。
• 文字列内の各文字 char について、以下の処理を行います。
  • count[char] を 1 減らし、length を 1 増やします。
  • count[char] が 0 でない、またはスタックが空でない間、次を繰り返します。
    • count[char] が 0 でない場合：char をスタックにプッシュしてループを抜けます（同じ文字が後続にも存在するため、ここでは区切りを確定できません）。
    • スタックが空でなく、スタック先頭の文字の残りカウントが 0 の場合：スタックからポップします。
    • それ以外の場合：ループを抜けます。
  • スタックが空になり、かつ count[char] が 0 になった時点で現在の部分が完結したことが分かるため、length を out に追加し、length を 0 にリセットします。
• すべての文字を処理し終えたら、out を返します。

アルゴリズムのポイント

この解法の鍵はスタックの活用にあります。ある文字がまだ文字列の後方に出現するなら、その文字を含む部分はその位置で終わることができません。そこで、未処理のまま残っている文字をスタックに積んでおき、現在位置以降にその文字がもう現れないこと（残りカウントが 0 になること）が確認できたら順に取り除いていきます。スタックが空になり、かつ現在の文字の残りカウントも 0 になった瞬間こそが、安全な分割地点です。

Pythonでの実装例

それでは、実際のコードを見てみましょう。

from collections import Counter

class Solution:
   def solve(self, s):
      count = Counter(s)
      out = []
      stk = []
      length = 0
      for char in s:
         count[char] -= 1
         length += 1
         while count[char] != 0 or stk:
            if count[char] != 0:
               stk.append(char)
               break
            if stk and count[stk[-1]] == 0:
               stk.pop()
            else:
               break
         if not stk and count[char] == 0:
            out += [length]
            length = 0
      return out

ob = Solution()
s = "momoplaykae"
print(ob.solve(s))

入力

"momoplaykae"

出力

[4, 1, 1, 4, 1]

計算量の評価

• 時間計算量：O(n)。文字列を一度だけ走査すればよく、スタックへのプッシュ・ポップも全体で高々 n 回です。
• 空間計算量：O(k)。k は異なる文字の種類数で、小文字英字に限定すれば最大 26 です。

まとめ

各文字の出現回数を事前にカウントし、スタックで未完了の文字を追跡することで、文字列を線形時間で効率的に分割できます。この考え方は、有名な「Partition Labels（区間ラベル分割）」問題などにも応用できる、覚えておくと非常に便利なテクニックです。