### Problem Statement

You are given a String number containing the digits of a phone number. To help you memorize the number, you want to divide it into groups of contiguous digits. Each group must contain exactly 2 or 3 digits. There are three kinds of groups:

• Excellent: A group that contains only the same digits. For example, 000 or 77.
• Good: A group of 3 digits, 2 of which are the same. For example, 030, 229 or 166.
• Usual: A group in which all the digits are distinct. For example, 123 or 90.

The quality of a group assignment is defined as 2 * (number of excellent groups) + (number of good groups). Divide the number into groups such that the quality is maximized, and return the result as a String, where each pair of consecutive groups is separated by a dash ('-'). If there are multiple ways to do this, return the one among them that results in the lexicographically earliest String.

### Definition

 Class: PhoneNumbers Method: bestNumber Parameters: String Returns: String Method signature: String bestNumber(String number) (be sure your method is public)

### Notes

-A String A comes before a String B lexicographically if A is a proper prefix of B, or if A has a smaller character at the first position where the strings differ. When comparing the characters, refer to the following list of characters in ascending order: '-', '0', '1', ..., '9'.

### Constraints

-number will contain between 2 and 50 characters, inclusive.
-Each character in number will be a digit ('0'-'9').

### Examples

0)

 `"5088638"`
`Returns: "50-88-638"`
 There are three possible ways to divide this number into groups: 508-86-38 (quality 0), 50-886-38 (quality 1) and 50-88-638 (quality 2). The last option is the best one.
1)

 `"0123456789"`
`Returns: "01-23-45-67-89"`
 No matter how you divide this number, the quality will be 0. Choose the division that comes earliest lexicographically.
2)

 `"09"`
`Returns: "09"`
 With a 2-digit phone number, there is only one choice.
3)

 `"54545454545454545454"`
`Returns: "54-545-454-545-454-545-454"`
 The best way to divide this number is to create six 3-digit good groups and one 2-digit usual group. Put the 2-digit group at the beginning to achieve the lexicographically earliest result.
4)

 `"00110001011100010111"`
`Returns: "00-11-00-010-11-10-00-101-11"`

#### Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=8609

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=12008&pm=8609

ivan_metelsky

#### Testers:

PabloGilberto , vorthys , Olexiy

Brute Force