Pythonで「a」の各グループの後に同じ長さの「b」のグループが続くかどうかを判定する方法

問題の概要

文字「a」と「b」の2種類のみで構成された小文字の文字列 s があるとします。このとき、連続する「a」のグループの後に、必ず同じ長さの連続する「b」のグループが続いているかどうかを判定するのが目的です。

例えば、入力が s = "abaaabbbaabbaabbab" の場合、文字列は次のようなグループに分割できます。

(ab) / (aaabbb) / (aabb) / (aabb) / (ab)

それぞれのグループで「a」の個数と「b」の個数が一致しているため、出力は True になります。

アルゴリズムの考え方

この問題は、カウンタを1つ使うことで効率的に解けます。「a」を読むたびにカウントを増やし、「b」を読むたびに減らしていき、各グループの区切りでカウントが 0 になっているかを確認するだけです。

具体的な手順は以下の通りです。

• a_count を 0、string_len を文字列 s の長さとして初期化する
• i を 0 に初期化する
• i < string_len の間、以下を繰り返す
  • i < string_len かつ s[i] が 'a' の間、a_count を 1 ずつ増やしながら i を進める
  • i < string_len かつ s[i] が 'b' の間、a_count を 1 ずつ減らしながら i を進める
  • この時点で a_count が 0 でなければ、False を返す（a と b の数が不一致）
• ループを抜けたら True を返す

この方法なら、文字列を一度走査するだけで済むため、計算量は O(n)、追加メモリも O(1) と非常に効率的です。

Pythonでの実装例

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

def solve(s):
    a_count = 0
    string_len = len(s)
    i = 0
    while i < string_len:
        while i < string_len and s[i] == 'a':
            a_count += 1
            i += 1
        while i < string_len and s[i] == 'b':
            a_count -= 1
            i += 1
        if a_count != 0:
            return False
    return True

s = "abaaabbbaabbaabbab"
print(solve(s))

入力

"abaaabbbaabbaabbab"

出力

True

まとめ

このアプローチでは、カウンタ a_count が各グループ内で「a」と「b」の対応関係を追跡します。もし「a」の数が「b」より多ければカウントは正の値のまま残り、逆に少なければ負になります。いずれの場合も False を返すことで、正確に条件を判定できます。