use dfs to try all possibilities. for each consecutive group in board, calculate how many balls needed to make group of 3+. if we have enough in hand, use them, remove group, shrink board (remove new groups of 3+), and recurse.
shrink function recursively removes groups of 3+ consecutive same characters. base cases: empty board returns 0, empty hand returns infinity. try all groups, take minimum.
algorithm
- find consecutive groups in board
- for each group, calculate need = 3 - group_length
- if hand has enough, use them and recurse
- shrink board after removing group
- return minimum balls needed
complexity
exponential time in worst case, but pruning helps. O(n) space for recursion stack where n is board length.