aloalgoFlip Coins Until All Heads
You have a row of coins, each showing either heads ('H') or tails ('T'). You can perform an operation: choose any coin and flip it. When you flip a coin at index i, it also flips its adjacent coins at i-1 (if i > 0) and i+1 (if i < n-1). The goal is to make all coins show heads ('H') using the minimum number of flips. Determine this minimum number. If it's impossible to make all coins heads, return -1.
Example 1
"HHT"
2
To make 'HHT' into 'HHH', we can flip the first coin (index 0). This changes 'HHT' -> 'TTH' (coins 0 and 1 flipped). Then, flip the second coin (index 1). This changes 'TTH' -> 'HHH' (coins 0, 1, and 2 flipped). Total 2 flips.
Example 2
"TTT"
1
To make 'TTT' into 'HHH', we can flip the middle coin (index 1). This changes 'TTT' -> 'HHH' (coins 0, 1, and 2 flipped). Total 1 flip.
Example 3
"HT"
-1
No sequence of flips can turn 'HT' into 'HH'. If we flip coin 0, it becomes 'TH'. If we flip coin 1, it becomes 'HH' (by flipping 0 and 1) but that doesn't mean it's possible. After careful consideration, it's impossible to achieve all 'H'.
"HHT"
2