Find the Closest Candidate String by Edit Distance
Company: Target
Role: Backend Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Take-home Project
## Find the Closest Candidate String by Edit Distance
### Problem
Implement `closestCandidates(candidates, queries) -> results`.
The edit distance between two strings is the minimum number of single-character insertions, deletions, and replacements needed to transform one string into the other. Every operation costs one.
For each query, find the candidate with minimum edit distance. Return both that distance and the chosen candidate's zero-based index.
### Function Contract
- `candidates` is a nonempty JSON-compatible array of lowercase ASCII strings.
- `queries` is a JSON-compatible array of lowercase ASCII strings.
- `results` has one element per query in query order.
- `results[q]` is `[minimumDistance, candidateIndex]`.
- If several candidates have the same minimum distance, choose the smallest candidate index. Duplicate candidate strings remain separate indexed candidates.
### Constraints
- `1 <= candidates.length <= 50`.
- `0 <= queries.length <= 50`.
- Every candidate and query has length between `0` and `100`, inclusive.
- Do not mutate either input array.
- Use exact unit-cost edit distance; transposition is not an allowed operation.
### Examples
```text
candidates = ["cat", "cut", "dog"]
queries = ["cot", "dogs", ""]
results = [[1, 0], [1, 2], [3, 0]]
```
```text
candidates = ["a", "a", "ab"]
queries = ["a"]
results = [[0, 0]]
```
```hint Compare prefixes
When deciding the distance for two prefixes, separate the cases where their final characters match from the three permitted edits when they do not.
```
### Requirements
- Compute the exact minimum for every candidate-query pair.
- Apply the smallest-index tie-break while scanning candidates.
- Explain the worst-case time complexity in terms of candidate count, query count, and string lengths.
- Explain how one edit-distance computation can reduce auxiliary space without changing its result.
### Discussion Prompts
1. Which base cases represent transforming an empty prefix?
2. Why does a greedy left-to-right character comparison fail?
3. What reusable work, if any, could be shared when many candidates have common prefixes?
Quick Answer: For each query string, select the indexed candidate with the smallest exact edit distance under a deterministic tie-break. The problem assesses dynamic-programming fundamentals, empty-prefix cases, duplicate candidates, memory optimization, complexity analysis, and the limits of greedy comparison.
Given a list of `candidates` and a list of `queries`, all lowercase ASCII strings, answer one question per query: which candidate is closest to it, and how far away is it?
The **edit distance** between two strings is the minimum number of single-character insertions, deletions, and replacements needed to transform one string into the other. Every operation costs exactly one. Transposition (swapping two adjacent characters) is **not** an allowed operation, so `"ab"` and `"ba"` are two edits apart, not one.
Implement `closestCandidates(candidates, queries)`:
- For each query, compute its edit distance to every candidate and keep the minimum.
- Return `[minimumDistance, candidateIndex]` for that query, where `candidateIndex` is the zero-based position of the chosen candidate inside `candidates`.
- `results` has exactly one entry per query, in query order.
**Tie-breaking.** When several candidates achieve the same minimum distance, return the **smallest** candidate index. Duplicate candidate strings are still separate candidates and keep their own positions, so a repeated string never merges with its earlier copy.
Neither input array may be mutated.
### Example 1
```text
Input: candidates = ["cat", "cut", "dog"], queries = ["cot", "dogs", ""]
Output: [[1, 0], [1, 2], [3, 0]]
```
- `"cot"` is one replacement away from `"cat"` (index 0) and one away from `"cut"` (index 1). Both tie at 1, so the smaller index 0 is returned.
- `"dogs"` is one deletion away from `"dog"` (index 2).
- `""` needs three deletions to reach any three-letter candidate, so all three tie at 3 and index 0 is returned.
### Example 2
```text
Input: candidates = ["a", "a", "ab"], queries = ["a"]
Output: [[0, 0]]
```
Indices 0 and 1 hold the same string `"a"` and both reach distance 0. The duplicate does not merge with the original, and the smaller index 0 is returned.
### Output format
`results[q]` is a two-element list `[minimumDistance, candidateIndex]`, both integers. `candidates` is never empty, so every query has an answer. When `queries` is empty, return the empty list `[]`.
Constraints
- 1 <= candidates.length <= 50
- 0 <= queries.length <= 50
- 0 <= candidates[i].length <= 100
- 0 <= queries[j].length <= 100
- candidates[i] and queries[j] consist of lowercase English letters only; the empty string is in range for both
- Every edit operation (insert, delete, replace) costs 1; transposition is not an allowed operation
- Neither input array may be mutated
- 0 <= minimumDistance <= 100 and 0 <= candidateIndex <= 49, so every returned value fits in a 32-bit signed integer
Examples
Input: (['a'], [])
Expected Output: []
Explanation: empty queries list
Input: (['a'], ['b'])
Expected Output: [[1, 0]]
Explanation: singleton candidate and singleton query
Hints
- Two prefixes either end in the same character or they do not. Settle that question first, and only then decide which of the three unit-cost edits is cheapest.
- What is the distance between an empty prefix and a prefix of length k? Those base cases are the entire first row and first column, and getting them wrong is the most common way this comes out off by one.
- Reread what should happen when two candidates are equally close. A scan that updates its best on `<=` and one that updates on `<` return different indices for the same input.