Find names similar by one swap
Company: DoorDash
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Technical Screen
##### Question
LeetCode 859. Buddy Strings – Given a target string and a list of strings, return all list entries that can match the target by swapping at most one pair of characters in each entry.
https://leetcode.com/problems/buddy-strings/description/
Quick Answer: This question evaluates string manipulation, character-frequency analysis, and algorithmic reasoning to determine near-matches under a single-character-swap constraint.
Given a target string and a list of strings, return all list entries that can become exactly the target after zero or one swap of two characters within the entry. The swap must be within the same string, and at most one such swap is allowed per entry. Preserve the original order of the list.
Constraints
- 1 <= len(target) <= 100000
- 0 <= len(words) <= 100000
- Sum of lengths of all words <= 200000
- All strings consist of lowercase English letters
- Return entries in their original order; duplicates are allowed
Solution
from typing import List
def find_similar_by_one_swap(target: str, words: list[str]) -> list[str]:
res: List[str] = []
tlen = len(target)
for w in words:
if len(w) != tlen:
continue
if w == target:
res.append(w)
continue
diff = []
for i, (a, b) in enumerate(zip(w, target)):
if a != b:
diff.append(i)
if len(diff) > 2:
break
if len(diff) == 2:
i, j = diff
if w[i] == target[j] and w[j] == target[i]:
res.append(w)
return res
Explanation
For each word, lengths must match. If a word equals the target, include it since zero swaps are allowed. Otherwise, collect indices where the characters differ. With exactly two such indices i and j, a single swap works if and only if word[i] equals target[j] and word[j] equals target[i]. Any other number of mismatches cannot be fixed by a single swap.
Time complexity: O(total_characters_across_words). Space complexity: O(1) extra (excluding output).
Hints
- Lengths must match; otherwise it's impossible.
- If a word already equals the target, include it (zero swaps allowed).
- Find indices where the word and target differ. Exactly two mismatches must cross-match to be solvable by one swap.
- Early-exit once more than two mismatches are found.