DNA testing is one of the most popular methods of establishing paternity. In such a test, you compare samples of DNA from the
man, the child, and the child's mother. For the purposes of this problem, assume that each sample is represented as a String of uppercase letters ('A'-'Z').
If half of the characters in the child's sample match the characters in the
corresponding positions in the man's sample, and the remaining characters in the child's sample match the characters in
the corresponding positions in the mother's sample, then the man is most likely the father. On the other hand, if it is
impossible to partition the child's sample such that half of the characters match the man's and the other half match the
mother's, then the man is definitely ruled out as the father.
For example, suppose the child's sample is "ABCD" and the mother's sample is "AXCY" (all quotes for clarity only).
The 'A' and 'C' in the child's sample must have come from the mother, so the 'B' and 'D' must have come from the father.
If the man's sample is "SBTD", then he is most likely the father, but if the man's sample is "QRCD", then he is definitely
not the father. Note in the latter case that the man was definitely ruled out even though half of his sample (the 'C' and
'D') did in fact match the child's.
Your method will take samples from the child and the mother, as well as samples from several men, and return the indices of the
men who cannot be ruled out as the father, in increasing order.
|