問題
問題文
英小文字からなる長さ N の文字列 S が与えられます。
S の空でない部分文字列であって、1 種類の文字のみからなるものの数を求めてください。 ただし、文字列として等しい部分文字列同士は、取り出し方が異なっても区別しません。
なお、S の空でない部分文字列とは、S の先頭から 0 文字以上、末尾から 0 文字以上削除して得られる文字列のうち、長さが 1 以上であるもののことをいいます。 例えば、
https://atcoder.jp/contests/abc329/tasks/abc329_cabやabcはabcの空でない部分文字列ですが、acや空文字列はabcの空でない部分文字列ではありません。
例を通して問題内容を理解
入力例
6
aaabaa
出力例
4
説明
S の空でない部分文字列であって、1 種類の文字のみからなるものは a, aa, aaa, b の 4 つです。 S から a や aa を取り出す方法は 1 通りではありませんが、それぞれ 1 回ずつしか数えないことに注意してください。
解決策
アルファベット２６個に全て対応すれば正解できそうだが、流石に面倒。
「なんかいい感じ」のがあるはず。
そこで、
ASCIIコードの
ord(‘a’) => 97
chr(97) => ‘a’
と、辞書型を使う。
実際にやってみた
max_counts = {chr(i): 0 for i in range(ord(‘a’), ord(‘z’)+1)}
これで、aからzまでの「辞書」が完成。
その後、辞書を更新する。
例えばakaaという文字列なら、
rle_S = [‘aka’, [1, 1, 2]]
なので、１文字目のaで
{ ‘a’ : 1, ~~~~}
になるが、3,4文字目のaaで
{ ‘a’ : 2, ~~~~}
に更新される。
あとは、辞書に載っている数字（＝文字列Sにおける、アルファベットごとの最大の連続回数）の合計すれば良い。
ソースコード
def rle(s):
n = len(s)
if n == 0:
return '', []
ret = ['', []]
c = s[0] # 1文字目がどこまで続くか
cnt = 0
for i in range(n):
if c == s[i]:
cnt += 1
else:
ret[0] += c # 1文字目の連続具合の記録
ret[1].append(cnt)
c = s[i] # 次の文字に移る
cnt = 1
if cnt > 0: # 例えばAAABBだったら、B,2を記録する場所
ret[0] += c
ret[1].append(cnt)
return ret
N = int(input())
S = input()
rle_S = rle(S)
# 各文字の最大連続回数を記録する辞書を初期化
max_counts = {chr(i): 0 for i in range(ord('a'), ord('z')+1)}
for i in range(len(rle_S[0])):
char = rle_S[0][i]
count = rle_S[1][i]
if max_counts[char] < count:
max_counts[char] = count
# 今後、'a'から'z'までの任意の文字の最大連続回数は max_counts['a'], max_counts['b'], ..., max_counts['z'] でアクセスできます
print(sum(max_counts.values()))
コメント