PROBLEM STATEMENT
ANAGRAM : Two Strings are ANAGRAMs of each other when one of the Strings can be
formed by reordering the characters of the other String. e.g. "TOPCODER" is an
anagram of "CODTOPER".
FIT : String strOne FITs into String strTwo, if strOne and strTwo are of equal
length and every character in strOne is smaller than its corresponding
character(in same position) in strTwo. e.g. "IEFBGCDH" FITs into "TOPCODER", as
'I' appears before 'T' in the alphabet, 'E' appears before 'O', 'F' appears
before 'P' and so on.
PACK : String strOne PACKs into String strTwo if an ANAGRAM of strOne FITs into
stringTwo. e.g. "BCDEFGHI" PACKS into "TOPCODER", as "IEFBGCDH", an ANAGRAM of
"BCDEFGHI", FITs into "TOPCODER".
CHAIN : A list of Strings form a CHAIN, if all Strings in the list except the
first one, PACK into all their predecessor Strings in the list. e.g.
{"TOPCODER","BCDEFGHI","AAAAAAAA"} form a CHAIN.
Create a class StringPack that contains the method maxChain, which takes a
String[] strList as input and returns the integer length of the longest
possible CHAIN that can be created using Strings from strList.
DEFINITION
Class : StringPack
Method : maxChain
Parameters: String[]
Return type: int
Method Signature( be sure method is public ): int maxChain(String[] strList)
NOTES
- If two Strings are the same, then they are to be considered as ANAGRAMs of
each other.
- Strings in strList could be of different lengths.
- Strings in a CHAIN need not be in the same order as in the the input strList.
- Any valid CHAIN should have a minimum of 2 Strings.
- If no CHAIN is possible return 0.
TopCoder will ensure the validity of the inputs. Inputs are valid if all of
the following criteria are met:
- strList has 0 to 50 elements (inclusive).
- Each String in strList is 1 to 50 characters in length, inclusive.
- All Strings only consist of capital letters ('A'-'Z').
EXAMPLES
Example 1
strList = {"TOPCODER","BCDEFGHI","AAAAAAAA","DYXWWXYZ","BDFGHIJK","BCDZZZZZ"}
Longest chain is
"DYXWWXYZ"
"TOPCODER" ( "CTOPODER" FITs into "DYXWWXYZ", ie. "TOPCODER" PACKs into
"DYXWWXYZ" )
"BCDEFGHI" ( "IEFBGCDH" FITs into "TOPCODER", ie. "BCDEFGHI" PACKs into
"TOPCODER" and its predecessors )
"AAAAAAAA" ( "AAAAAAAA" PACKs into "BCDEFGHI" and all its predecessors )
Hence your method should return 4.
Example 2
strList = {"ABCD","UVWZ","DAUZ"}
Your method should return 2.
Example 3
strList = {"JSP","USTVW","NCFGH","ABCDE","KIJ"};
Your method should return 3.
Example 4
strList = {"BDCA","LAWN","PANE","CZCC"}
Your method should return 0.
Example 5
strList = {"A","D","B","D"}
Your method should return 3.
Example 6
strList =
{"AB","BC,"CD","DE","EF","FG","GH","HI","IJ","JK","KL","LM","MN","NO","OP","PQ",
"AA"};
Your method should return 16.
Example 7
strList =
{"ABABABABABABABABABABABABABABABABABABA","BCDEFGHIJKLMNOCDEFGHIJDEFGHIKLMNOPQRS"
};
Your method should return 2.