Data scientists at Amazon are working on a utility for genome sequencing algorithms. The utility finds anagram patterns in pairs of DNA sequence strings.
A pair of DNA strings is special if they can be made anagrams after removing any number of occurrences of at most one character from each DNA string.
Given n pairs of DNA strings, for each pair, determine whether it is special. Return a list of boolean values, one for each pair, where True means the pair is special.
Example
Given n = 1, and strings dna1 = "safddadfs" and dna2 = "famafmss".
The strings are anagrams after removing all occurrences of character 'd' from dna1 and character 'm' from dna2.
Return [True].
Note: It is not required that all instances of a character be removed. For example, given "aab" and "ba", one 'a' can be removed from "aab" to leave "ab".
Function Description
Complete the function getSequence in the editor below.
getSequence has the following parameter(s):
string dna[n][2]: the pairs of DNA sequencesReturns
boolean[n]: true if the pair is special and false otherwiseSample Input For Custom Testing
2
2
abcee acdeedb
sljffsaje sljsjeSample Output
1
0This problem asks whether each pair of DNA strings can become anagrams after deleting any number of occurrences of at most one character from each string. The key idea is to compare character frequency differences: positive differences must be fixed by removing one character from the first string, while negative differences must be fixed by removing one character from the second string. Because each side can only choose one character type to delete, we only need to verify that the positive and negative mismatches each involve at most one distinct letter. A 26-element frequency array makes the solution linear in the string length per pair.
