Pythonで最長の「素敵な」部分文字列(nice substring)を見つける方法

文字列 s が与えられたとき、その中から最長の「素敵な(nice)」部分文字列を見つける問題を考えてみましょう。ある文字列が「素敵」とみなされるのは、そこに含まれるすべての英字について、大文字と小文字が両方とも登場する場合です。条件を満たす部分文字列が複数存在するときは、最も早く出現するものを返します。

たとえば、入力が s = "ZbybBbz" の場合、答えは "bBb" になります。この部分文字列には大文字の B と小文字の b が両方含まれているためです。

アルゴリズムの流れ

この問題は、開始位置と終了位置のすべての組み合わせを調べる総当たり(ブルートフォース)方式で解くことができます。手順は以下のとおりです。

• cur_max(現在の最大長)を -1 で初期化する
• res(結果の文字列)を空文字列で初期化する
• 開始位置 i を 0 から文字列の末尾まで順に動かす
  • c := s[i] とし、大文字用の集合 upper と小文字用の集合 lower を新しく作成する
  • c が小文字なら lower に追加する
  • c が大文字なら、小文字に変換してから upper に追加する
  • 終了位置 j を i+1 から文字列の末尾まで順に動かす
    • s[j] についても同じ要領で対応する集合へ追加する
    • upper == lower(大文字と小文字がきちんと対応している)場合
      • j - i > cur_max であれば、cur_max を更新し、res に s[i:j+1] を代入する
• ループが完了したら res を返す

ここでのポイントは、大文字を一度小文字に揃えてから集合に格納することです。これにより、「同じ英字の大文字と小文字が両方そろっているか」を、単純な集合の等価比較だけで簡単に判定できます。

Pythonでの実装例

def solve(s):
    cur_max = -1
    res = ""
    for i in range(len(s)):
        c = s[i]
        upper = set()
        lower = set()
        if c.islower():
            lower.add(c)
        if c.isupper():
            upper.add(c.lower())
        for j in range(i + 1, len(s)):
            c = s[j]
            if c.islower():
                lower.add(c)
            if c.isupper():
                upper.add(c.lower())
            if upper == lower:
                if j - i > cur_max:
                    cur_max = j - i
                    res = s[i:j + 1]
    return res

s = "ZbybBbz"
print(solve(s))

入力

"ZbybBbz"

出力

bBb

計算量の目安

開始位置と終了位置の組み合わせは O(n²) 通りあります。各ステップでは集合への追加と比較を行いますが、英字は26種類と固定されているため集合比較は実質定数時間となり、全体の計算量は O(n²) と評価できます。より高速に処理したい場合は、分割統治法を利用する方法や、各英字ごとに「片方のケースしか現れない位置」を区切りとして扱うことで O(26n) に近い線形時間で解く手法も知られています。