Statistics

PROBLEM STATEMENT

For this problem, 'letter' refers to an uppercase alphabetic character, 'A'-'Z'.

Given a String[] oddConstraints and a String[] evenConstraints, what is the
minimum number of letters you would have to remove to make every element in
OddConstraints contain an odd number of letters and every element in
EvenConstraints contain an even number of letters?  If you remove a letter, you
must remove it from every element that contains it in both String[] parameters.

Each individual element of oddConstraints and evenConstraints should be
considered a set of unique uppercase letters; no letter will be duplicated
within the same element, but a letter may appear in more than one element.

Return the minimum number of unique letters you would have to remove (this
could be 0) from the String[] parameters to make every element in
oddConstraints have an odd number of letters and every element in
evenConstraints have an even number of letters, or -1 if it is not possible.

Example:
String[] oddConstraints = {"ACDE", "BCDE"}
String[] evenConstraints = {"EC", "ED"}

Every element in EvenConstraints already has an even number of letters, but the
OddConstraints don't have an odd number of letters. ("ACDE" and "BCDE" each
have 4 letters, and 4 isn't odd)
If you remove every instance of 'C', 'D', and 'E' you are left with:

oddConstraints = {"A", "B"}
evenConstraints = {"", ""}

Since 0 is considered even, the requirements have been met, and there is a
possible solution by removing 3 unique letters ('C', 'D', and 'E').

However, you can also remove just the 'A's and 'B's to leave:

oddConstraints = {"CDE", "CDE"}
evenConstraints = {"EC", "ED"}

Here you only had to remove 2 unique letters.
Since these are the only two ways to meet the requirements by removing letters,
you would return the minimum number of unique letters removed (2).

DEFINITION

Class: OddsOrEven
Method: minRemoved
Parameters: String[], String[]
Returns: int
Method signature (be sure your method is public):  int minRemoved(String[]
oddConstraints, String[] evenConstraints)

NOTES
- remember to return -1 if there is no way to make the constraints valid
- In the following hints, ^ refers to exponentiation
- Hint 1: looping through every possible combination of letters (2^26) is
impractical, even with optimizations- be careful of timeouts
- Hint 2: oddConstraints and evenConstraints are limited to 7 elements each
(for a total maximum of 14).  2^14 would be much more manageable

TopCoder will ensure the validity of the inputs.  Inputs are valid if all of
the following criteria are met:
- oddConstraints will contain between 0 and 7 elements, inclusive
- evenConstraints will contain between 0 and 7 elements, inclusive
- each element of oddConstraints and evenConstraints will contain only the
uppercase letters 'A'-'Z'
- each element of oddConstraints and evenConstraints will be a set- in other
words, a letter may appear in multiple elements, but will appear at most once
in each element.
- each element of oddConstraints will contain between 1 and 26 letters, inclusive
- each element of evenConstraints will contain between 1 and 26 letters,
inclusive

EXAMPLES

(1)
oddConstraints = {"ACDE", "BCDE"}
evenConstraints = {"EC", "ED"}

Your method would return 2

(2)
oddConstraints = {}
evenConstraints = {"ABC"}

Your method would return 1

(3)
oddConstraints = {"AB", "CD", "EF", "GH", "IJ", "KL", "MN"}
evenConstraints = {"S", "T", "U", "V", "W", "X", "Y"}

Your method would return 14 

(4)
oddConstraints = {"THE", "QUICK", "BROWN", "FOX", "JUMPED", "OVER", "THE"}
evenConstraints = {"LAZY", "DOGS", "BUT", "COULDNT", "RUN", "VERY", "FAST"}

Your method would return 5

(5) 
oddConstraints = {"IMPOSBLE"}
evenConstraints = {"IMPOSBLE"}

Your method would return -1

(6)
oddConstraints = {"ZABCDEFGHIJ", "ZABCDEKLMNO", "ZFGHIJKLMNO", "ZPQRSTX",
"ZPQUVWY", "ZRSTXUVWY"}
evenConstraints = {"ABCDE", "KLMNO", "ZGHIJ", "ZPQR", "ZPQU", "ZRSTX"}

Your method would return 6

(7)
oddConstraints = {"ABC"}
evenConstraints = {"AB"}

Your method would return 0