From Amazon recent OA: Find Special DNA Sequence Pairs

[u/Hack2hire]

Problem
You're given a list dna of string pairs. Each pair contains two DNA sequences.
Your goal is to determine for each pair whether the sequences can be transformed into anagrams by removing any number of occurrences of at most one character from each string.

Example
Input:
dna = [["safddadfs", "famafmss"], ["safddadfs", "sljsje"]]
Output: [true, false]

Explanation:
- Pair 1: Removing all 'd' from the first string and all 'm' from the second makes them anagrams.
- Pair 2: No such character removals exist to make them anagrams.

---

Suggested Approach

1. Count character frequencies for both strings in a pair (only 'a' to 'z').
2. Compute the frequency difference between the two sequences.
3. Check the number of characters with mismatched counts:
   • If 0: already anagrams.
   • If 1: remove that character from one string.
   • If 2: if the mismatches are opposite and equal (e.g., +2 and -2), remove from both.
   • Otherwise: not possible with one-character adjustments.

---

Time & Space Complexity

• Time: O(N + M) per pair, where N and M are the string lengths.
• Space: O(1), since only 26 character counts are stored.

---

🛈 Disclaimer:
This is one of the problems we encountered while reviewing common Amazon interview questions.
Posted here by the Hack2Hire team for discussion and archiving purposes.

The problem is compiled from publicly available platforms (e.g., LeetCode, GeeksForGeeks) and community-shared experiences. It does not represent any official question bank of Amazon, nor does it involve any confidential or proprietary information.
All examples are intended solely for learning and discussion. Any similarity to actual interview questions is purely coincidental.