Explanation

Approach

A “paving stone group” is a maximal contiguous run of # characters. To count the groups, it suffices to count the leftmost cell of each run.

A cell \(i\) (1-indexed) is the leftmost cell of a group if and only if:

• \(S_i = \) #, and
• \(i = 1\) or \(S_{i-1} = \) .

So the answer is the number of cells that are # and whose previous cell is not #. We scan \(S\) once from left to right and count indices \(i\) such that \(S_i = \) # and (\(i = 1\) or \(S_{i-1} \neq \) #).

Proof of Correctness

For each paving stone group \(B\), let \(\ell(B)\) denote its leftmost cell.

• \(\ell(B)\) is #, and its left neighbor either does not exist or is . (if it existed and were #, it would belong to the same group, contradicting that \(\ell(B)\) is the leftmost). Hence \(\ell(B)\) satisfies the counting condition.
• Conversely, any cell \(i\) satisfying the condition is #, so it belongs to some group; since its left neighbor is not #, the group cannot extend further left, so \(i\) is that group’s leftmost cell.

Thus cells satisfying the condition correspond bijectively to leftmost cells of groups. Distinct groups have distinct leftmost cells, so the number of such cells equals the number of groups.

Complexity

• Time: \(O(N)\)
• Space: \(O(N)\) to store the input string, \(O(1)\) additional space for the scan

Since \(N \leq 100\), this is easily fast enough.