モグラの穴 — 解説

問題の概要

長さ \(N\) の文字列 \(S\) が与えられ、# はモグラの穴があるマス、. は穴がないマスを表します。# が連続して並ぶ部分列(連続区間)のうち、最も長いものの長さを求めます。# が一度も現れない場合は 0 を出力します。

アルゴリズム

文字列を左から右へ一度だけ走査し、2 つの変数を管理します。

• cur: 現在処理中の位置を右端とする連続する # の個数
• ans: これまでに見つかった最大の連続区間の長さ

各文字 c について:

• c == '#' ならば cur を 1 増やし、ans = max(ans, cur) で最大値を更新する。
• c == '.' ならば連続が途切れたので cur を 0 にリセットする。

走査終了後の ans が答えです。

C++ 実装では文字を 1 文字ずつ読み込んで処理するため、文字列全体を保持する必要がありません。Python 実装では入力文字列 \(S\) をそのまま保持して走査します。

正しさの証明

処理開始前は cur = 0 とします。文字が # なら直前の連続区間を1文字延ばすので cur を1増やし、. なら連続区間が途切れるので0に戻します。したがって各位置の処理後、cur はその位置で終わる連続区間の長さです。

ans は0で初期化し、各 # の処理時に cur との最大値を取ります。すべての連続区間の右端を必ず調べるため、終了時には最長の長さが得られます。# がない場合は0のままで、これも正しい答えです。

タイブレークについて

答えは「最大長」という一意な整数値であり、複数の区間が同じ最大長を持つ場合でも出力すべき値は 1 つだけなので、タイブレークは不要です。

計算量

• 時間計算量: \(O(N)\) (各文字を定数時間で 1 回ずつ処理)
• 空間計算量: C++ 実装は入力を 1 文字ずつ読むため補助空間 \(O(1)\)。Python 実装は入力文字列の保持に \(O(N)\)、それ以外の補助空間は \(O(1)\)。