Find minimum tanks to cover all houses
Company: Palo
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are given a string `S` representing a street:
- `'H'` = a house
- `'-'` = an empty plot where you may place a water tank
A house is considered **covered** (able to collect rainwater) if there is a water tank placed **adjacent** to it (either immediately to its left or right).
You may place tanks only on empty plots (`'-'`). Your task is to compute the **minimum number of tanks** needed so that **every house** in `S` is covered. If it is impossible to cover all houses, return `-1`.
Example:
- Input: `S = "-H-HH--"`
- One optimal placement is `"-HTHHT-"` (where `'T'` denotes a tank), which uses `2` tanks.
Implement a function that returns the minimum number of tanks required (or `-1` if impossible).
Quick Answer: This question evaluates a candidate's proficiency in algorithm design, specifically greedy strategies and string/array manipulation for coverage and optimization under local adjacency constraints.
Place the fewest tanks on empty plots so every house has an adjacent tank, or return -1.
Constraints
- S contains H and -
Examples
Input: ('-H-HH--',)
Expected Output: 2
Explanation: Prompt-style example.
Input: ('H',)
Expected Output: -1
Explanation: Impossible.
Input: ('H-',)
Expected Output: 1
Explanation: One tank to the right.
Input: ('-H--H',)
Expected Output: 2
Explanation: Greedy right placement.
Hints
- Scan left to right; prefer placing a tank to the right to cover possible future houses.