Pythonで2つの文字列の間に存在する辞書順の文字列を見つける方法

問題の概要

2つの文字列 S と T が与えられたとき、S より辞書順で大きく、T より辞書順で小さい同じ長さの文字列が存在するかどうかを判定します。該当する文字列が存在しない場合は -1 を返します。

たとえば、入力が S = "bbb"、T = "ddd" の場合、出力は "bbc" となります。"bbb" の直後に辞書順で来る文字列は "bbc" であり、これは "ddd" よりも小さいためです。

辞書順の定義

S = S1S2…Sn があるインデックス i について S1 = T1, S2 = T2, …, Si-1 = Ti-1, Si < Ti を満たすとき、S は T = T1T2…Tn より辞書順で小さいと定義されます。つまり、先頭から順に文字を比較していき、最初に異なる文字が出現した時点で大小関係が確定するというルールです。

解法のアプローチ

この問題は「S の直後の文字列(辞書順で S の次に位置する文字列)を求める」という発想で解けます。数値のカウントアップと同じ要領で、末尾の文字から順に確認し、インクリメントできるなら1つ増やし、'z' に達していたら 'a' に戻して一つ前の文字へ繰り上がります。

アルゴリズムの手順

1. 文字列の長さ n を取得します。
2. i を n - 1 から 0 まで逆順にループします。
   • string[i] が 'z' 以外の場合:
     ASCII コードを1つ増やした文字に置き換え、結合した文字列を返します。
   • string[i] が 'z' の場合:
     'a' に戻して(繰り上がり)一つ前の文字へ進みます。

Pythonでの実装例

def find_next(string):
    n = len(string)
    for i in range(n - 1, -1, -1):
        if string[i] != 'z':
            k = ord(string[i])
            string[i] = chr(k + 1)
            return ''.join(string)
        string[i] = 'a'

S = "bbb"
T = "ddd"
S = list(S)
res = find_next(S)
if res != T:
    print(res)
else:
    print(-1)

入力

"bbb", "ddd"

出力

bbc

コードのポイント

• リストへの変換: Python の文字列はイミュータブル(変更不可)なため、list() で文字のリストに変換して操作し、最後に join() で文字列に戻しています。
• T との比較: 求めた次の文字列が T と一致する場合、「S と T の間」に文字列は存在しないため -1 を出力します。
• 計算量: 各文字を高々1回ずつ処理するため、時間計算量は O(n) と非常に効率的です。
• 注意点: すべての文字が 'z' の場合(例:"zzz")は繰り上がりが完了せず関数が None を返すため、実運用ではこのエッジケースの扱いにも留意が必要です。