【ABC043D】アンバランス / Unbalanced【ARC059B】
問題概要
文字列sの中に、過半数が同じ文字となる2文字以上の部分文字列t(アンバランスな部分文字列)は存在するか判定せよ。tが存在するならその区間を、しないなら-1 -1を出力せよ。
制約
- 2<=|s|<=105
- sは小文字のアルファベットのみからなる。
考察
tは2文字以上なので、とりあえず順番にどんな文字列がアンバランスなのか考えてみる。
2文字の場合は、
aaやppといったAA型
以上、1通りのみ。
3文字の場合は、
dadやmomといったABA型zooやseeといったABB型ddrやmmoといったAAB型aaaやzzzといったAAA型
以上、4通りだが、内ABB型、AAB型、AAA型はAA型を含んでいるため、実際はABA型のみを考えればよさそう。
4文字の場合は、
aaaaやzzzzといったAAAA型aaazやzzzaといったAAAB型aazaやzzazといったAABA型azaaやzazzといったABAA型zaaaやazzzといったBAAA型
以上、5通りだが、全てAA型を含んでいるため考えなくてよさそう。
同様に5文字以降も考えていくと、AA型かABA型を含んでいそうなので、この2通りを判別する。
ACコード(Python3🐍)
s=input() for i in range(len(s)-1): if s[i]==s[i+1]: print(i+1,i+2) exit() for i in range(len(s)-2): if s[i]==s[i+2]: print(i+1,i+3) exit() print(-1,-1)
