Pythonで文字列内の単語間スペースを均等に再配置するプログラム

問題の概要

文字列 s が与えられ、その中にはいくつかの単語が複数のスペースを挟んで配置されています。各単語は少なくとも1つのスペースで区切られているものとします。ここで、隣り合う単語どうしの間に入るスペースの数がすべて同じになり、しかもその間隔が最大になるように、スペースを再配置することを考えます。すべてのスペースを均等に振り分けられない場合は、余ったスペースは文字列の末尾にまとめて置くこととします。

たとえば、入力が s = " I love programming " の場合、出力は "I  love  programming" となります。元の文字列に含まれていた4つのスペースが、単語と単語の間に2つずつ均等に分配されているのがわかります。

解き方の手順

この問題を解くために、以下のステップに従って処理を進めます。

• res := 空文字列（結果を格納する変数）

• total_sp := s 内に含まれるスペースの総数

• suff_sp_cnt := total_sp（末尾に回すスペースの残数を管理する変数）

• text_array := s を分割して得られる単語のリスト

• num_words := text_array の要素数

• もし num_words が 1 ならば、
  res := text_array[0] に total_sp 個のスペースを連結した文字列とし、res を返します（単語が1つしかないため、すべてのスペースを末尾に置きます）

• sep_size := total_sp ÷ (num_words − 1) の商（小数点以下切り捨て）

• sep := sep_size 個のスペースからなる区切り文字列

• text_array の各要素 i に対して次の処理を繰り返します。
  res := res + i
  res := res + sep
  suff_sp_cnt := suff_sp_cnt − sep_size

• suff_sp_cnt := suff_sp_cnt + sep_size（最後の単語の後に余計に付いた sep の分を戻します）

• res の左右両端にある余分なスペースを取り除きます

• res の末尾に suff_sp_cnt 個のスペースを連結します

• res を返します

Pythonによる実装例

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

def solve(s):
    res = ""
    total_sp = s.count(" ")
    suff_sp_cnt = total_sp

    text_array = s.split()
    num_words = len(text_array)

    if num_words == 1:
        res = text_array[0] + total_sp * " "
        return res

    sep_size = total_sp // (num_words - 1)
    sep = sep_size * " "

    for i in text_array:
        res += i
        res += sep
        suff_sp_cnt -= sep_size

    suff_sp_cnt += sep_size
    res = res.strip()
    res += suff_sp_cnt * " "

    return res

s = " I love programming "
print(solve(s))

入力

" I love programming "

出力

I  love  programming

ポイント解説

このアルゴリズムの鍵は、単語の数を n、スペースの総数を m としたとき、単語間の基本間隔を m // (n - 1) で求める点です。割り切れずに余ったスペースは変数 suff_sp_cnt で管理され、最後に文字列の末尾へ一括して追加されます。また、ループではすべての単語の後ろに一旦区切りスペースを付与していますが、strip() で末尾の不要なスペースを除去したうえで、正しい余剰スペースを付け直すことで、期待どおりの整形結果を得られます。処理全体の計算量は文字列長に比例する O(n) であり、非常に効率的です。