TopCoder problem "PhoneNumbers" used in TCO08 Qual 2 (Division I Level Two)

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.



Method signature:String bestNumber(String number)
(be sure your method is public)


-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'.


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


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

Problem url:

Problem stats url:




PabloGilberto , vorthys , Olexiy

Problem categories:

Brute Force