Single-Mutation Control Partners
For each string, smallest index of one differing at exactly one position
A genetics lab has an ordered collection of DNA strands. Each strand uses only the letters A, C, G, and T, and all strands have the same length.
For each strand, the lab wants a control partner that differs from it at exactly one position. A substitution at one position qualifies; insertions and deletions are not allowed. Two identical strands do not qualify, even when they appear at different indices.
Given the array strands, return an integer array of the same length. At index i, return the smallest zero-based index j such that strands[i] and strands[j] differ at exactly one position. Return -1 if no such partner exists.
Partners are chosen independently: the same strand may serve as the partner for multiple strands. If strands is empty, return an empty array.
Examples
Example 1
Input: strands = ["ACG","ATG","ACG","ACT","TTG"] Output: [1,0,1,0,1]
The two occurrences of ACG are identical, so they cannot partner with each other. ATG and ACT each differ from ACG at one position. When several partners qualify, their order in the input determines which one is selected.
Example 2
Input: strands = ["AAAA","CCCC"] Output: [-1,-1]
AAAA and CCCC differ at every position, so neither is a single-mutation control for the other.
Constraints
- 0 <= strands.length <= 4000
- If strands is nonempty, all strands have the same length L, where 1 <= L <= 20.
- Every character in every strand is one of A, C, G, or T.
- Duplicate strands are allowed.
The reference solutions encode A, C, G, and T as base-4 digits. Masking a position sets its digit to zero, and a separate map is used for each position. These encodings are exact, not probabilistic hashes. With L <= 20, all encoded values are exactly representable by JavaScript numbers. The intended complexity is O(nL) time and O(nL) auxiliary space.
Hints
Show hint 1Hint 1
Two strands that differ at one position become identical when that position is hidden. Include the hidden position in the grouping key.
Show hint 2Hint 2
An identical strand must be rejected. For each group, consider retaining the earliest representative and the earliest representative whose full strand differs from it.
Follow-up questions
What an interviewer might ask once you have a working solution.
- How would you count all unordered pairs of strands that differ at exactly one position?
- How would you adapt the approach to process incoming strands and find only partners that appeared earlier?
Practice this with an AI interviewer
Explain your approach out loud, write Python or JavaScript, run it against hidden tests (including large inputs), and get a scored debrief.
Start this problem