Pythonで指定された条件を満たす辞書順最小の文字列を見つける方法

問題の概要

長さnの整数配列Aが与えられます。A[i]は、ある文字列sの先頭から(i+1)文字分の接頭辞に含まれる異なる文字の種類数を表します。このとき、与えられた配列Aの条件をすべて満たす辞書順最小の文字列を見つける必要があります。使用できる文字は小文字の英字[a-z]のみで、条件を満たす文字列が存在しない場合は-1を返します。

例えば、入力が A = [1, 1, 2, 3, 4] の場合、出力は「aabcd」になります。各接頭辞における異なる文字数は以下の通りです。

• prefix[0](a): 1種類
• prefix[1](aa): 1種類
• prefix[2](aab): 2種類
• prefix[3](aabc): 3種類
• prefix[4](aabcd): 4種類

これらの条件を満たしつつ、辞書順で最小となるのが「aabcd」です。

解法の考え方

この問題は貪欲法で解くことができます。ポイントは以下の通りです。

• 辞書順最小にするため、最初の文字は必ず「a」にします。したがって A[0] が 1 でない場合は答えが存在しません。
• A[i] - A[i-1] の差分が 0 の場合、異なる文字数を増やすことはできないため、すでに使われている最小の文字「a」を追加します。
• 差分が 1 の場合は新しい文字が必要です。まだ使っていない文字のうち最小のものを順番に割り当てます(b、c、d…)。
• 差分が 1 より大きい、負になる、または A[i] が 26 を超える場合は条件を満たす文字列が存在しないため、-1 を返します。

アルゴリズムの手順

1. n を配列Aのサイズとし、character を「a」、string を空文字列で初期化します。
2. n < 1 または A[0] が 1 でない場合は -1 を返します。
3. string に character を連結し、character を次の文字に進めます。
4. i = 1 から n-1 まで以下を繰り返します。
   • difference = A[i] - A[i-1] を計算します。
   • difference > 1、difference < 0、または A[i] > 26 の場合は -1 を返します。
   • difference == 0 の場合は string に「a」を追加します。
   • それ以外の場合は string に character を追加し、character を次の文字に進めます。
5. string を返します。

Pythonでの実装例

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

def get_smallest_string(A):
    n = len(A)
    character = 'a'
    string = ""
    if (n < 1 or A[0] != 1):
        return -1
    string += str(character)
    character = chr(ord(character) + 1)
    for i in range(1, n):
        difference = A[i] - A[i - 1]
        if (difference > 1 or difference < 0 or A[i] > 26):
            return -1
        elif (difference == 0):
            string += 'a'
        else:
            string += character
            character = chr(ord(character) + 1)
    return string

A = [1, 1, 2, 3, 4]
print(get_smallest_string(A))

入力

[1, 1, 2, 3, 4]

出力

aabcd

計算量

時間計算量・空間計算量はともに O(n)(nは配列Aの長さ)です。配列を一度走査するだけで答えが求まるため、非常に効率的な解法といえます。