Pythonで長さk・距離nとなる辞書式最小の小文字文字列を求めるプログラム

問題の概要

2つの整数 n と k が与えられたとき、長さが k で「距離」がちょうど n になる、辞書式順序で最も小さい小文字の英字列を見つけることを考えます。

ここでいう「距離」とは、文字列を構成する各文字のアルファベット上の番号（a=1、b=2、…、y=25、z=26）の合計のことです。

具体例

たとえば入力が n = 15、k = 3 の場合、出力は「aam」となります。「aam」は長さ3で、その距離が 1 + 1 + 13 = 15 を満たす、辞書式順序で最小の文字列だからです。

解き方のアプローチ

この問題は貪欲法（グリーディー法）で効率よく解けます。まず全文字を「a」（番号1）で初期化し、余った距離（credit）を後ろの文字から順に最大限まで割り振っていきます。後ろの文字から大きくすることで、前の文字をできるだけ小さく保てるため、結果として辞書式順序で最小の文字列が得られます。

具体的な手順は以下の通りです。

• dist：サイズ k の配列を作成し、すべて 1 で初期化する
• credit := n − k（追加で割り振るべき残りの距離）
• i := k − 1（末尾のインデックスから処理を開始）
• credit > 0 の間、次を繰り返す
  • val := min(credit, 25)（1文字に追加できる最大値は25）
  • dist[i] := dist[i] + val
  • credit := credit − val
  • i := i − 1
• dist の各要素 d に対して chr(d − 1 + ord('a')) で文字へ変換し、連結して返す

Python実装例

以下のコードで実際の動作を確認できます。

def solve(n, k):
    dist = [1] * k

    credit = n - k

    i = k - 1
    while credit > 0:
        val = min(credit, 25)
        dist[i] += val
        credit -= val
        i -= 1

    return "".join(chr(d - 1 + ord("a")) for d in dist)

n = 15
k = 3
print(solve(n, k))

入力

15, 3

出力

aam

このアルゴリズムの計算量は O(k) であり、文字列の長さに対して線形時間で動作するため、非常に効率的です。