Minimum Water Tanks to Serve All Houses
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
-andH.
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.