Pythonで「bird」に並べ替えられる長さ4の部分文字列の個数を求める方法

すべて小文字で構成された文字列 S が与えられます。このとき、文字を並べ替えると "bird" という単語になる長さ4の部分文字列が、文字列全体にいくつ含まれているかを求めます。

たとえば、入力が "birdb" の場合、出力は 2 になります。これは、先頭の「bird」と2文字目以降の「irdb」の2つの部分文字列が、それぞれ並べ替えることで "bird" を作れるためです。

解法の考え方

この問題は、次の手順で解きます。

• カウンタ変数 cnt を 0 で初期化します。
• i を 0 から len(s) - 3 まで動かし、長さ4の部分文字列の開始位置を順番に調べます。
• 各開始位置について、'b'・'i'・'r'・'d' の出現回数を記録する配列 bird = [0, 0, 0, 0] を用意します。
• j を i から i + 3 まで動かしながら s[j] がどの文字かを判定し、対応する要素を 1 ずつ増やします。
• 4文字分の集計が終わった時点で bird が [1, 1, 1, 1] と一致していれば、その部分文字列は並べ替えて "bird" を作れるため、cnt を 1 増やします。
• すべての位置を調べ終えたら、cnt を返します。

実装例

以下は、上記の考え方を Python で実装したコードです。

def number_of_occurrence(s):
    cnt = 0
    for i in range(0, len(s) - 3):
        bird = [0, 0, 0, 0]
        for j in range(i, i + 4):
            if s[j] == 'b':
                bird[0] += 1
            elif s[j] == 'i':
                bird[1] += 1
            elif s[j] == 'r':
                bird[2] += 1
            elif s[j] == 'd':
                bird[3] += 1
        if bird == [1,1,1,1]:
            cnt += 1
    return cnt

s = "birdb"
print(number_of_occurrence(s))

入力

"birdb"

出力

2

計算量と補足

外側のループが最大 n 回（n は文字列の長さ）、内側のループは固定の 4 回しか走らないため、全体の計算量は O(n) と非常に効率的です。

また、Python の標準ライブラリ collections.Counter を使うと、同じ処理をより簡潔に書くこともできます。

from collections import Counter

def number_of_occurrence(s):
    target = Counter("bird")
    return sum(Counter(s[i:i+4]) == target for i in range(len(s) - 3))

どちらの方法でも、各部分文字列に含まれる 'b'・'i'・'r'・'d' がそれぞれちょうど1回ずつ現れているかどうかを判定することで、正しく個数を数えられます。