NOTE: This problem statement contains superscripts that may not display properly if viewed outside of the applet.
There is a horizontal row of N squares, each of which either contains a counter or is empty. A set of counters in this row is called a group if it meets all of the following requirements:
- They form a contiguous part of the row.
- The square immediately to the left of the leftmost counter in the set is empty, or the leftmost counter in the set is in the leftmost square of the row.
- The square immediately to the right of the rightmost counter in the set is empty, or the rightmost counter in the set is in the rightmost square of the row.
In one move, we can take any group and simultaneously move all of its counters one square to the right (only if the rightmost counter in the group is not in the rightmost square of the row), or one square to the left (if the leftmost counter in the group is not in the leftmost square of the row). The cost of such a move is C2, where C is the number of counters in the group.
You will be given a String board that represents the initial row from left to right. Each character of board represents the content of a single square and is either uppercase 'X' (counter) or '.' (empty). Your goal is to have all the counters in the row form exactly one group. Return the minimum possible total cost required to achieve this. |