コンテンツにスキップ

yukicoder contest 517 A - Happy End

サイト
yukicoder
コンテスト
yukicoder contest 517
問題
A - Happy End

英大文字からなる長さ NN の文字列 SS があります(5≤N≤3×1055 \le N \le 3 \times 10^5)。文字列 TT が「良い」とは、TT の末尾 5 文字が HAPPY で、それ以外の場所に HAPPY が部分文字列として現れないことをいいます。

SS の 1 文字を別の文字に書き換える操作を繰り返して SS を良い文字列にするとき、操作回数の最小値を求めてください。

末尾 5 文字は必ず HAPPY にしなければならないので、HAPPY と異なる文字の個数だけ書き換えが必要です。

次に、末尾以外に現れる HAPPY をすべて壊します。ここで大事なのは、HAPPY 同士は重なって現れないことです。HAPPY の中で H は先頭にしかないので、HAPPY の途中から別の HAPPY が始まることはありません。

そのため、末尾以外に現れる HAPPY は、末尾の HAPPY とも互いにも重なりません。重ならない HAPPY を 1 つ壊すには少なくとも 1 文字書き換える必要があり、1 回の書き換えで 2 つ同時に壊すこともできません。よって、末尾以外に現れる HAPPY の個数が、この段階で必要な操作回数の下限になります。

この下限は達成できます。各 HAPPY の 1 文字を、HAPPY に含まれない文字(たとえば Z)に書き換えればよいです。HAPPY に含まれない文字を含む位置からは新しい HAPPY が生まれないので、書き換えによって別の場所に HAPPY ができることはありません。

答えは 2 つの段階の操作回数の和で、計算量は O(N)O(N) です。

Python
N = int(input())
S = list(input())
ans = 0
for i in range(1, 6):
if S[-i] != "HAPPY"[-i]:
S[-i] = "HAPPY"[-i]
ans += 1
for i in range(N - 5):
if S[i : i + 5] == list("HAPPY"):
S[i + 4] = "Z"
ans += 1
print(ans)

前半のループで末尾 5 文字を HAPPY にそろえ、後半のループで末尾以外の HAPPY を見つけるたびに最後の Y を Z に書き換えています。