問題概要
文字列$s$の中に, 過半数が同じ文字となる2文字以上の部分文字列$t$(アンバランスな部分文字列)は存在するか判定せよ.
$t$が存在するならその区間を, しないなら-1 -1を出力せよ.
制約
- $2 \leq |s| \leq 10^5$
- $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通りを判別する.
提出コード(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)