TopCoder problem "CandidateKeys" used in SRM 386 (Division I Level One , Division II Level Two)

Problem Statement

A database table consists of a set of columns called attributes, and a set of rows called entries. A superkey is a set of attributes such that each entry's values for those attributes forms a unique ordered set. That is, for any superkey, each pair of entries differs in at least one of the attributes contained within the superkey. A candidate superkey is a superkey such that no proper subset of its attributes forms a superkey.

Return a int[] with exactly two elements. The first element should be the number of attributes in the smallest candidate superkey of the table, and the second element should be the number of attributes in the largest candidate superkey of the table. If there is no valid candidate superkey, return an empty int[] instead.

The input is described by a String[] table. Each String in table represents one entry, while characters contained in the String are attribute values for that entry.

Definition

Class:	CandidateKeys
Method:	getKeys
Parameters:	String[]
Returns:	int[]
Method signature:	int[] getKeys(String[] table)
(be sure your method is public)

Notes

A proper subset of a superkey is a set of attributes that is formed by removing one or more attributes from the superkey.

Constraints

table will contain between 2 and 50 elements, inclusive.

Each element of table will contain between 1 and 10 characters, inclusive.

Each element of table will contain the same number of characters.

Each character in table will be an uppercase letter ('A'-'Z').

Examples

{
"ABC",
"ABC",
"ABC"
}

Returns: { }

Since all entries are the same, there is no set of attributes that can differentiate between them. Therefore, this table has no candidate superkeys.

{
"ABC",
"ABD",
"ABE"
}

Returns: {1, 1 }

There are four superkeys here:

{column 0, column 1, column 2}

{column 0, column 2}

{column 1, column 2}

{column 2}

Note that the fourth superkey is a subset of all the other superkeys, so it is the only candidate superkey.

{
"ABC",
"ACD",
"BBE"
}

Returns: {1, 2 }

{"A","B"}

Returns: {1, 1 }

{
"AABB",
"BABA",
"CAAB",
"DAAA",
"EBBB",
"FBBA",
"GBAB",
"HBAA"
}

Returns: {1, 3 }

Problem url:

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

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=11120&pm=8444

Writer:

eleusive

Testers:

PabloGilberto , Olexiy , lovro , ivan_metelsky

Problem categories:

Brute Force, Simple Search, Iteration