ペアリング（文字列連結）

問題

$ N $ 個の文字列 $ s_0, s_1, …, s_{N-1} $ が与えられます。

これらの文字列を好きな順序で並べた後、連結して１つの文字列を作ります。

作った文字列に“AB”が最大で何個含まれるかを求めて下さい。

[条件]
🔹文字列の数 $ N $ は $ 1 $ 以上 $ 10^4 $ 以下の整数
🔹$ s_i $ は英大文字
🔹$ s_i $ の長さは $ 2 $ 以上 $ 10 $ 以下

解法・ソースコード

この問題は連結部の“AB”の個数を最大化する問題と言えます。

$ N $ 個の文字列 $ s_0, s_1, …, s_{N-1} $ は次の４パターンに分類できます。

🔹パターン１：B***A（左端が”B”で、右端が”A”）
🔹パターン２：****A（左端が”B”ではなく、右端が”A”）
🔹パターン３：B****（左端が”B”で、右端が”A”ではない）
🔹パターン４：*****（左端が”B”ではなく、右端も”A”ではない）

パターン４はほかの文字列と連結して“AB”となることはないので無視します。

パターン１、２、３の個数をそれぞれ $ c_1, c_2, c_3 $ とします。

「理論的にこれより多く作るのは不可能である」という上界を考えます。

“A”の個数は全部で $ c_1 + c_2 $ 個であり、“B”の個数は全部で $ c_1 + c_3 $ 個です。

したがって、$ min(c_1 + c_2, c_1 + c_3) = c_1 + min(c_2, c_3) $ よりも多くの“AB”を作ることは絶対できません。

$ c_2 = c_3 = 0 $ の場合、パターン１同士が連結した部分でしか “AB”をつくれませんので、答えは $ max(c_1 - 1, 0) $ となります。

また、$ c_2 $ と $ c_3 $ のうち少なくとも一方が $ 1 $ 以上である場合には、$ c_1 + min(c_2, c_3) $ 個の“AB”を作ることができます。

上記を踏まえると以下の手順で問題を解くことができます。

🔹各文字列 $ s_0, s_1, …, s_N-1 $ にすでに含まれている“AB”の個数の総和を $ T $ とする。
🔹各文字列を４パターンに分類する。（ $ c_1,c_2,c_3 $ の定義は前述の通り）
🔹$ c_2 = c_3 = 0 $ の場合、$ T + max(c_1 - 1, 0) $ 個の“AB”ができる。
🔹$ c_2 $ と $ c_3 $ いずれかが $ 1 $ 以上の場合、$ T + c_1 + min(c_2, c_3) $ 個の“AB”ができる。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#--------- 入力例 -----------
n = 3
lst = ['ABCA', 'XBAZ', 'BAD']
#----------------------------
t = 0                   # それぞれの文字列に含まれる"AB"の個数の総和（連結前）
c1, c2, c3 = 0, 0, 0    # パターン１、２，３の個数

for s in lst:
    # 各文字列に含まれる"AB"の個数
    t += s.count("AB")
    if s.startswith('B') and s.endswith('A'):   # パターン１の個数
        c1 += 1
    elif s.endswith('A'):                       # パターン２の個数
        c2 += 1
    elif s.startswith('B'):                     # パターン３の個数
        c3 += 1

# パターン２とパターン３の数に応じて結果を出力
if c2 == 0 and c3 == 0:
    print(t + max(c1 -1, 0))
else:
    print(t + c1 + min(c2, c3))

[実行結果]

2

“ABCA”、”BAD”、”XBAZ”の順に結合して、”ABCABADXBAZ”を作ると、“AB”が２つできることが確認できます。