PhoneNumbers | Topcoder Archive

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

```
"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.
```
"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.
```
"09"
```
```
Returns: "09"
```
With a 2-digit phone number, there is only one choice.
```
"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.

"00110001011100010111"

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

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.