Mole Holes — Editorial

Problem Overview

You are given a string \(S\) of length \(N\), where # denotes a square containing a mole hole and . denotes a square without one. Find the length of the longest contiguous run (consecutive segment) of # characters. If there is no # at all, print 0.

Algorithm

Scan the string once from left to right, maintaining two variables:

• cur: the number of consecutive # characters ending at the current position
• ans: the maximum run length found so far

For each character c:

• If c == '#', increment cur by 1 and update ans = max(ans, cur).
• If c == '.', the run is broken, so reset cur to 0.

After the scan, ans is the answer.

The C++ implementation reads and processes one character at a time, so the whole string never needs to be stored. The Python implementation keeps the input string \(S\) and iterates over it.

Proof of Correctness

Initially, cur is zero. A # extends the previous run by one character, so we increment cur; a . breaks the run, so we reset cur to zero. Thus, after every position, cur is the length of the run ending at that position.

We initialize ans to zero and take its maximum with cur whenever a # is processed. Every run has a right endpoint that is examined, so the final maximum is the longest run length. If there is no #, ans remains zero, which is also correct.

Tie-breaking

The answer is a single integer — the maximum length — so even if several runs share the same maximum length, only one value must be printed. No tie-breaking is needed.

Complexity

• Time: \(O(N)\) — each character is processed once in constant time.
• Space: the C++ implementation reads one character at a time and uses \(O(1)\) auxiliary space. The Python implementation uses \(O(N)\) to hold the input string and \(O(1)\) otherwise.