Find names similar by one swap

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/

Filter Strings by One Swap Similarity

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

Examples

Example 1

Input: target = "ab", words = ["ba", "ab", "aa", "abc", "ac", "bb"]
Output: ["ba", "ab"]

Explanation: ba -> swap indices (0,1) to get ab; ab already equals target; others cannot match with at most one swap or have different length.

Example 2

Input: target = "abcd", words = ["abdc", "acbd", "abcc", "abcd", "dacb", "badc"]
Output: ["abdc", "acbd", "abcd"]

Explanation: abdc and acbd each need one swap to become abcd; abcd requires zero swaps; abcc has one mismatch; dacb and badc have more than two mismatches.

Hints

1. Lengths must match; otherwise it's impossible.
2. If a word already equals the target, include it (zero swaps allowed).
3. Find indices where the word and target differ. Exactly two mismatches must cross-match to be solvable by one swap.
4. Early-exit once more than two mismatches are found.

Approach

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)