ARC113 C - String Invasion (500)
前から置換を行うと一種類の文字列にすぐに統一されてしまうので後ろから置換を行う
事前に後ろからその位置までのそれぞれの文字の出現回数を累積和で求めておく
後ろから置換の条件を満たしている部分を見つける度に以下を行う
i番目の文字の場合、$ n -i - 2を答えに加える
i+2文字目から以前の置換位置までの、今回連続している文字と同じ文字の回数だけ答えから引く
その文字を置換する場合は、3文字とも既に同じ文字になっているので新たに処理はできない
直前の置換で連続していた文字と同じ場合
nから直前の置換位置までの長さを答えから引く
前回の置換位置より後ろは既に今回置換する文字と同じになってしまっているので新たに処理できない
一文字ずつ見て処理するだけなので$ O(|S|)