Pythonで指定した数値を持つ辞書順最小の文字列を求めるプログラム

問題の概要

2つの整数 n と k が与えられます。求めるのは、長さが n で、数値(合計値)がちょうど k に等しい、辞書順で最小の文字列です。

ここでいう「数値」とは、小文字アルファベットをアルファベット順の位置(1始まり)に対応させた値のことです。「a」は1、「b」は2、「c」は3……というように対応し、「z」は26になります。また、小文字のみで構成される文字列の数値は、その文字列を構成する各文字の数値の総和として定義されます。

たとえば、入力が n = 4、k = 16 の場合、出力は「aaam」になります。1 + 1 + 1 + 13 = 16 となり、条件を満たす長さ4の文字列の中で、これが最も辞書順の小さいものだからです。

解き方の考え方(貪欲法)

この問題は、文字列を後ろの文字から決めていく貪欲法で効率的に解くことができます。ポイントは以下の通りです。

• 残りの文字数を n、残りの合計値を k とするとき、現在の位置にはできるだけ大きい文字を選ぶ。
• ただし、残りの n−1 文字がそれぞれ最低でも「a」(数値1)を持てるように、選択できる最大値は min(26, k − n + 1) に制限する。
• これを繰り返し、最後に文字列を反転すると答えが得られる。

アルゴリズムの手順

• 空の文字列を用意する
• n > 0 の間、以下を繰り返す
  • letter ← min(26, k − n + 1)
  • 文字列に、アルファベットの letter 番目の文字を連結する
  • k ← k − letter
  • n ← n − 1
• 文字列を反転して返す

Pythonでの実装例

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

def solve(n, k):
    string = ""
    while n > 0:
        letter = min(26, k - n + 1)
        string += chr(letter + ord('a') - 1)
        k -= letter
        n -= 1
    return string[::-1]

n = 4
k = 16
print(solve(n, k))

入力

4, 16

出力

aaam

コードの解説

chr(letter + ord('a') - 1) の部分では、数値 letter を対応するアルファベット文字へ変換しています。ord('a') は文字「a」の文字コード(97)を返すため、letter の値に応じた文字を正しく取得できます。

また、string[::-1] はPythonのスライス記法による文字列の反転処理です。文字列を末尾側から構築しているため、最後に反転することで正しい順序の出力になります。

このアルゴリズムの計算量は、文字列の長さ n に対して O(n) と非常に効率的で、長い文字列に対しても高速に動作します。