Algorithm for identifying correct subset
You can solve this by looking for a maximum cardinality matching in a bipartite graph, then covering remaining vertices arbitrarily.

Make a bipartite graph:


In the left part of the graph, make a vertex for every capital letter.
In the right part of the graph, make a vertex for every combination of lowercase letter and number.
For each record, make an edge (which necessarily goes from a vertex on the left to one on the right) corresponding to the two vertices covered by the record.


Now run an algorithm for finding a maximum cardinality matching in a bipartite graph, such as the Hopcroft-Karp maximum flow algorithm.  This picks a subset of edges (records) that together cover the most possible distinct combinations of capital letter and (lowercase letter + number).  That is, each chosen record hits both a capital letter, and a (lowercase letter + number) pair that are not hit by any other chosen record.

If the matching saturates (touches) every vertex, you have a "perfect" solution!  Otherwise, for each remaining vertex, you need to pick a record incident on that vertex -- it doesn't matter which record you pick, because it definitely won't be incident on any untouched vertices on the other side (if it was, then it would have been included in the matching already).