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.

 

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

Writer:

ivan_metelsky

Testers:

PabloGilberto , vorthys , Olexiy

Problem categories:

Brute Force