Wells Beside the Houses

Medium

A village street is described by a string street: the character 'H' is a house and '.' is an empty plot. Plots are numbered from zero. The village wants to dig wells, and a well can only go on an empty plot. A house has water if there is a well on at least one of its neighbouring plots, directly to its left or directly to its right. Return the smallest number of wells that gives every house water, or -1 if that is impossible.

Example 1

street="H.H..H" → 2

A well on plot 1 serves houses 0 and 2, and a second well on plot 4 serves house 5. One well is not enough.

Example 2

street=".HH." → 2

The houses stand side by side, so each needs its own well on the outer side: on plots 0 and 3.

Example 3

street="H.HHH." → -1

House 3 is squeezed between houses 2 and 4 with no empty plot next to it, so the answer is -1.

Constraints

1 ≤ len(street) ≤ 10⁵
street consists only of the characters 'H' and '.'

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Greedy String Dynamic Programming

Similar problems

Brackets With Wildcards Medium Bead String Without Twins Medium Alternate After Rotating Medium Binary Number Under a Cap Medium Digit Pieces Under a Cap Medium

Input

street="H.H..H"

Expected

Run checks the first 3 tests in your browser. Submit checks all 94 tests on the server, hidden ones included.