ABC098-B - Cut and Count を解く

ABC098-B - Cut and Count

与えられた文字列を一箇所で切断したとき

どちらにも含まれている文字が最大でいくつになるかを求める問題

Python のスライスの機能を使って文字列を分断していく

書き方がうろ覚えであったのでひとまず実験のコードを書いてみた

実験用コード

# 入力
N=int(input())
S=input()

# 実験
for i in range(1,N):
  print(S[:i])
  print(S[i:])
  print('-----------')

 

実行結果

$ python3 test.py
6
aabbca
a
abbca
-----------
aa
bbca
-----------
aab
bca
-----------
aabb
ca
-----------
aabbc
a
-----------

上記の通り、文字列 S に対しては S[:i] とS[i:] を使うことで

i 番目（0-index）で文字を分断できることがわかった

文字列を2つに分断したあとは

両文字列に共通して含まれる文字をカウントして

一致した回数の最大数を求める

ただし、今回は一致する文字の種類数が問われているので

重複する文字はあらかじめ set を使って取り除くことにする

以上を踏まえて書いたコードを以下に示す

提出したコード

# 入力
N=int(input())
S=input()

mx=0
for i in range(1,N):
  l1=list(set(S[:i]))
  l2=list(set(S[i:]))
  
  c=0
  for x in l1:
    if l2.count(x)>0:
      c+=1

  # 最大値更新
  mx=max(mx,c)

# 出力
print(mx)

提出結果はACでした