TopCoder problem "CardRemover" used in SRM 259 (Division I Level Three)



Problem Statement

    

There are some cards placed in a line. Each card is characterized by the three distinct letters written on it.

The conformity-level of two cards is the number of distinct letters that are common to both cards. For example, the conformity-level of "ABC" and "ACD" is 2 because the letters 'A' and 'C' are common to both cards, and the conformity-level of "ABC" and "DFE" is 0 because the two cards share no common letters.

You can remove a card if the conformity-level of its left neighbor and its right neighbor is greater than or equal to 2. Once a card is removed its left and right neighbors become neighbors themselves. The leftmost and rightmost cards are never removed.

Given a String[] cards, determine the maximum quantity of cards that you can remove.

 

Definition

    
Class:CardRemover
Method:calculate
Parameters:String[]
Returns:int
Method signature:int calculate(String[] cards)
(be sure your method is public)
    
 

Constraints

-cards will have between 2 and 50 elements, inclusive.
-Each element of cards will contain exactly 3 characters.
-Each element of cards will contain three distinct uppercase letters ('A'-'Z').
 

Examples

0)
    
{"ABC",
 "CDE",
 "ABC",
 "CDE",
 "ABC"}

Returns: 3
You should not remove the third card before the second or the fourth.
1)
    
{"ABC",
 "CDE",
 "EFG",
 "GHI",
 "IJK"}

Returns: 0
You can't remove anything.
2)
    
{"ADR",
 "FDB",
 "ABC",
 "CDE",
 "ABD"}

Returns: 3

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=8012&pm=4468

Writer:

Andrew_Lazarev

Testers:

PabloGilberto , lbackstrom , brett1479 , Olexiy

Problem categories:

Dynamic Programming