Pythonで文字列を4つの異なる部分文字列に分割できるかどうかを判定する方法

問題の概要

文字列 s が与えられたとき、それを空でなく、かつ互いにすべて異なる4つの部分文字列に分割できるかどうかを判定するのが、この記事のテーマです。

たとえば入力が s = "helloworld" の場合、["hel", "lo", "wor", "ld"] のように4つの異なる部分文字列へ分割できるため、出力は True になります。

解法の考え方

この問題は以下の手順で解くことができます。

• 文字列の長さが 10 以上であれば、即座に True を返す(理由は後述)
• 長さが 10 未満の場合は、分割位置となる 3 つの境界 i、j、k を全探索する
• 各組み合わせで 4 つの部分文字列を作成し、すべてが互いに異なるかどうかをチェックする
• 条件を満たす分割が見つかれば True、最後まで見つからなければ False を返す

なぜ長さ 10 以上なら必ず分割できるのか?

長さ 10 以上の任意の文字列は、先頭から順に「1文字・2文字・3文字・残り全部」という 4 つの部分に分割できます。長さの異なる文字列同士は決して一致しないため、この分割では 4 つの部分文字列が必ず互いに異なることになります。これが「長さ 10 以上なら常に True を返してよい」という性質の根拠です。

Pythonでの実装例

それでは、実際のコードを見てみましょう。ここでは重複チェックに set を使うことで、比較処理を簡潔にしています。

def solve(s):
    if len(s) >= 10:
        return True
    n = len(s)
    for i in range(1, n):
        for j in range(i + 1, n):
            for k in range(j + 1, n):
                sub1 = s[:i]
                sub2 = s[i:j]
                sub3 = s[j:k]
                sub4 = s[k:]
                # 4つの部分文字列がすべて異なるかどうかをsetで判定
                if len({sub1, sub2, sub3, sub4}) == 4:
                    return True
    return False

s = "helloworld"
print(solve(s))

入力と出力

入力:

"helloworld"

出力:

True

計算量のポイント

全探索が行われるのは文字列の長さが 9 以下の場合だけです。このとき分割位置の選び方は高々 C(8, 3) = 56 通りしか存在せず、アルゴリズムは事実上一定時間で完了します。さらに、長さ 10 以上のケースは O(1) で即座に判定できるため、どんなに長い文字列でも非常に高速に動作する点が大きな魅力です。