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
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.