Pythonで文字列がaⁿbⁿパターンに一致するかどうかを判定する方法

文字列 s が与えられたとき、その文字列が aⁿbⁿ パターンに従っているかどうかを判定する方法を解説します。このパターンとは、「a」がn個続き、その後に「b」がn個続く形式の文字列のことです。たとえば n = 3 の場合、文字列は "aaabbb" となります。

たとえば、入力が s = "aaaaabbbbb" の場合、この文字列は a⁵b⁵ の形に一致するため、出力は True になります。

解決のアプローチ

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

• まず、文字列 s の長さを取得します。
• 先頭から順に文字を走査し、「a」以外の文字が出現した位置でループを抜けます。これにより、「a」が連続している区間の長さがわかります。
• その位置 i が文字列全体の長さのちょうど半分（i * 2 == size）であるかを確認します。半分でなければ、「a」と「b」の個数が等しくないため False を返します。
• 残りの部分（位置 i 以降）がすべて「b」で構成されているかを確認し、一つでも異なる文字があれば False を返します。
• すべての条件を満たせば True を返します。

実装例

以下のコードで実際の動作を確認してみましょう。

def solve(s):
    size = len(s)
    for i in range(size):
        if s[i] != 'a':
            break
    if i * 2 != size:
        return False
    for j in range(i, size):
        if s[j] != 'b':
            return False
    return True

s = "aaaaabbbbb"
print(solve(s))

入力

"aaaaabbbbb"

出力

True

コードのポイント

このアルゴリズムの計算量は O(n) で、文字列を最大2回走査するだけなので非常に効率的です。

なお、注意点として、空文字列や「a」「b」以外の文字が含まれる場合も正しく処理されます。また、"aabbb" のように「a」と「b」の個数が異なる場合や、"ba" のように順序が逆の場合にも False が返されるため、aⁿbⁿ パターンの厳密な判定が可能です。