AtCoder ABC 098 B – Cut and Count Python解説

スポンサーリンク

Cut and Count

英小文字からなる長さ N の文字列 S が与えられます。 この文字列を一箇所で切断して、文字列 X と Y に分割します。 このとき、「X と Y のどちらにも含まれている文字」の種類数を最大化したいです。 文字列を切断する位置を適切に決めた際の「X と Y のどちらにも含まれている文字」の種類数の最大値を求めてください。

AtCoder Beginner Contest 「Cut and Count」

与えられる文字列Sの長さは最大で100なので、文字列をスライスで1文字ずつずらしながら、XとYの共通文字を数えたいと思います。

共通の文字の調べ方としては、文字列の文字がこの問題ではすべて英小文字で与えられるので、あらかじめアルファベットのリストを用意して、ひとつずつXとYに含まれるか確認します。

n = int(input())
s = input()

cnt = 0
ans = 0

alphabet = ["a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n",
            "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z"]

for i in range(1, n+1):
    cnt = 0
    for letter in alphabet:
        if letter in s[: i] and letter in s[i: ]:
            cnt += 1
    ans = max(cnt, ans)
print(ans)

外側のfor文でスライスの位置を管理しています。続く内側のfor文で、アルファベットのaからzまでを取り出し、XとYに含まれるか確認し、XとY共に含まれていたらcnt+1します。