読者です 読者をやめる 読者になる 読者になる

D - アンバランス / Unbalanced

問題
D: アンバランス / Unbalanced - AtCoder Beginner Contest 043 | AtCoder

文字列について、過半数を超えている文字があれば、その文字列はアンバランスであるという。
文字列Sが与えられる。Sの部分文字列について、アンバランスなものがあれば、その始点と終点を1-indexedで出力せよ。そのような部分文字列がなければ、代わりに"-1 -1"を出力せよ。
N \le 10^5


解法
連続する2文字、または連続する3文字についてのみ、アンバランスかどうか調べれば良い。アンバランスな文字列に含まれる部分文字列で、2文字または3文字のアンバランスな部分文字列を含まないものが存在するかどうかは、公式の解説にあるように背理法的に考えれば良い。2文字または3文字のアンバランスな文字列を含まないアンバランスな文字列を考える。過半数となる文字を c として、他の文字を _ とする。十分にcを採用したとして、c _ _ c _ _ c _ _ c ... のような形になり、cの数は過半数とならない。