Minimum Water Tanks to Serve All Houses

Reported in interviews at DRW

Problem statement

You are given a string $S$ describing a street. Each character is a house H or an empty plot -. You may place water tanks on empty plots. A house collects rainwater if a tank sits directly adjacent to it (immediately left or right). Write solution(S) returning the minimum number of tanks needed so every house is served, or $-1$ if it is impossible.

Constraints:

  • $1 \le N \le 20$ (as transcribed; the original was likely larger); $S$ contains only - and H.

Examples:

  • $S = $ -H-HH-- $\to 2$ (e.g. -HTHHT-).
  • $S = $ H $\to -1$ (no plot for a tank).
  • $S = $ HH-HH $\to -1$ (the outer houses have no adjacent empty plot).
  • $S = $ -H-H-H-H-H $\to 3$ (e.g. -HTH-HTHTH).
Show hint

If you walk the street from one end, what is the smartest place to put a tank for the first house that still needs one?

Relevant roles: ML Engineer, Forward Deployed Engineer and AI Engineer.

Related free problems