Problem Statement
With some simplification, a DNA sequence can be described as a string in which each character is 'C', 'G', 'A', or 'T'.
There are three basic types of DNA mutations:
- Insertions: a character gets added somewhere into the string. For example, if we have the string "CAGAT", the strings "CAGGAT", "ACAGAT", and "CAGATG" are among the strings that can be produced by a single insertion.
- Deletions: a character gets removed from the string. For example, a deletion can transform "CAGAT" to "AGAT", "CGAT", "CAAT", "CAGT", or "CAGA".
- Substitutions: a character gets replaced by a different character. For example, from "CAGAT" we may obtain "CAAAT", "CAGAG", "CAGGT", or many other strings.
You are given two DNA sequences A and B. We say that these sequences are similar if B can be obtained from A by at most two mutations (one after another).
Return "similar" if A and B are similar, or "distinct" if they aren't.
Definition
- Class:
- SimilarDNA
- Method:
- areSimilar
- Parameters:
- String, String
- Returns:
- String
- Method signature:
- String areSimilar(String A, String B)
- (be sure your method is public)
Notes
- The quotes are not a part of the return value.
- The return value is case-sensitive: the string must be in all lowercase, exactly as written in the statement.
Constraints
- A will have between 1 and 50 characters, inclusive.
- B will have between 1 and 50 characters, inclusive.
- Each character of A and B will be 'C', 'G', 'A', or 'T'.
Examples
"AAAAA"
"AACAACA"
Returns: "similar"
B can be produced from A by performing two insertions, each adding a 'C'.
"AACAACA"
"AAAAA"
Returns: "similar"
The same as example 0 but in reverse: now we need two deletions.
"AACAACA"
"AAGAATA"
Returns: "similar"
Two substitutions.
"CGATCGAT"
"CATCGAG"
Returns: "similar"
A deletion (the first occurrence of 'G') and a substitution (the last character changes from 'T' to 'G').
"CGATCGAT"
"CGATCGAT"
Returns: "similar"
Zero mutations needed.
"CGATATATAGGA"
"GGATATACCATA"
Returns: "distinct"
Here we would need much more than two mutations.
"AAAAA"
"AA"
Returns: "distinct"
"CTTAATTCTCCCATCATGGATGC"
"AAAGGCGACATACGAGTCTAAGAACTATAGCGTTAG"
Returns: "distinct"
"CGCCATTACATACGGATGGTGGCGATCAT"
"C"
Returns: "distinct"
"CACACGGTGTTCCGGACGCTCCCACAG"
"GACTACCTTAATGCCTTCTCATCGAAGTCCTTACGACATT"
Returns: "distinct"
"CTAAT"
"GCCATAACCTACACTAAGAGTATTACGTCCTTTAACACGTATTGAACTTG"
Returns: "distinct"
"TCGGCTTCGTGTCGCTCTTTACTCCTTCGTTTCTATGATCGTAC"
"TCACTCGGAACCAGTGT"
Returns: "distinct"
"TCTGACACGCGGCGGGCCGTACTAGACACCGGACATATTT"
"TTCGACTCTCCATCAGTTTCGGCTAGGACCACCAAGGAAGGTCA"
Returns: "distinct"
"ATCTTATACTGATCCTGTACAATCCTACGGGTTGACCCA"
"GATGATCTAACCCACGCCCTTGCATACCAACTTTA"
Returns: "distinct"
"CATACTTGACCGGGCCTTTTGGTTAGCCGGCCGCGATTCGGGCGATT"
"ATTGCTTTTAAAATTCAGTTCCCAAGCAAG"
Returns: "distinct"
"CTTAGAAATCGGGAGTAGACGGGAGGCATGTGGTCTACAC"
"GATCAACTA"
Returns: "distinct"
"GAAACGATACGGAAACAGCAGGTTCTCGCTAGTGCGGCTAAA"
"CATGCCAT"
Returns: "distinct"
"CCATG"
"CCTT"
Returns: "similar"
"GAGGG"
"CGAGAG"
Returns: "similar"
"AGAAG"
"TATGAAG"
Returns: "similar"
"ACTA"
"TCA"
Returns: "similar"
"TAT"
"AT"
Returns: "similar"
"AG"
"G"
Returns: "similar"
"TCACA"
"TCAC"
Returns: "similar"
"GTTCC"
"GTCC"
Returns: "similar"
"T"
"C"
Returns: "similar"
"T"
"AG"
Returns: "similar"
"ATAA"
"GGAA"
Returns: "similar"
"CAGA"
"AGA"
Returns: "similar"
"CG"
"GC"
Returns: "similar"
"GGGG"
"GAC"
Returns: "distinct"
"T"
"TC"
Returns: "similar"
"GGGC"
"GGTGC"
Returns: "similar"
"ACA"
"TA"
Returns: "similar"
"AT"
"A"
Returns: "similar"
"A"
"T"
Returns: "similar"
"GTTGA"
"TA"
Returns: "distinct"
"T"
"CT"
Returns: "similar"
"CATAG"
"GTAG"
Returns: "similar"
"AACTA"
"AACT"
Returns: "similar"
"CA"
"A"
Returns: "similar"
"AGAG"
"AGGAG"
Returns: "similar"
"CAAG"
"CCAG"
Returns: "similar"
"GTACC"
"GGTACG"
Returns: "similar"
"AACA"
"AAAC"
Returns: "similar"
"GGGTG"
"GGGTAGG"
Returns: "similar"
"GGT"
"GT"
Returns: "similar"
"TG"
"TTGC"
Returns: "similar"
"CTGTG"
"GTGT"
Returns: "similar"
"ATAAT"
"ACAAT"
Returns: "similar"
"TT"
"T"
Returns: "similar"
"GTAC"
"GTC"
Returns: "similar"
"CA"
"CG"
Returns: "similar"
"AGGGC"
"AGCGGGC"
Returns: "similar"
"CGG"
"CC"
Returns: "similar"
"CAATTGAGGCCCTTGGACGGTTTCTGAGTTGGGGACGTGATTTC"
"CATCGAGGCCCTTGGACGGTTTCTGAGTTGGGGACGTTGATTTC"
Returns: "distinct"
"GTGCCCAATACCATCATTGCAATCTCTCGAGGGGTCACTGC"
"CACACCTGCCGCACCAAATGATGCACTTGTCTTGAACCAAGTTACT"
Returns: "distinct"
"ACGCCAGTTGCCAACAAAAGCACTTATGACTTAGGCGCAT"
"ACGACCAGTTGCCAACAAAGCACTTATGACTTAGGCGCAT"
Returns: "similar"
"GGGAGTCCGTAATTTTGCTTAATGGTTCAAGTGGCTTGTCAGG"
"GGAGTCCGTAATTCTGCTTAATGGTTCAAGTGGCTTTCAGG"
Returns: "distinct"
"AAATCGCGCAATCCATAAAGTGGAACTATTCAATATGGTTTCATCAAGC"
"GTTCGATTGCGCGTAAAATGAACTTGCATTCTGTTCCCTATGCG"
Returns: "distinct"
"CCTTATAGCCAGATAAAGGGGGGTAAGTATCCTCCGTGTC"
"CCTTTATAGCCAGATACAAGGGGGGTAAGTATCCTCCGTGTC"
Returns: "similar"
"GGTTCGACTTAGGGAAACGCGAATGTTCGCGTATTTTGAGTCC"
"GGGTCGACTTAGGGTAAACGCTATGTTAGCGTATTTTGCAGTCC"
Returns: "distinct"
"CCCCCCCCGCGATCCATGGGACTCCTTCCTTGCTATAGATTGATAT"
"CCCCCCCCGGCGATCCATGCCGTAGTCCTTCATTGCTATAGATTGATAT"
Returns: "distinct"
"AGGCCAGTACTTGTCATTGAACAGCAACTTATGCCTACGTGGA"
"AGGCCAGTACTGTGTCATTGAAGCATTTTGCCTACGTGAA"
Returns: "distinct"
"GTCCTTACATTGTGACCACCTTAATACATGGTCAAACTGCACTT"
"GTCCTTACATTGTGACACTTAATTATATGGTTAACTGCATCTT"
Returns: "distinct"
"CCGACCTATGTCATTAGAAAAGAATCGACGTCATCCCGAGTTCGT"
"CCGACCTATGTCATTAGAAATGAATCGACGTCATCCCGAGTTCGT"
Returns: "similar"
"GGAACGTCGTTTGAACTTAGCTACGATGGGTGGTTACAATTCCGCTCCT"
"CGACCCACGGTGTTTCCGATTATAGCTGTAATCAACACTCCACGCCC"
Returns: "distinct"
"GGGCAATTTTGGTTAGTGTGGTCGCCCGAGATAGCTAGCATCGC"
"GGGCAATTTTAGTTAGTGTAGTCGCCCGAGATAGCTAGCATCGC"
Returns: "similar"
"TCACATGACATTTAGACCGAATCCCTTAGGTAGTGGCTGCACCC"
"TCACATGACATTTAGACCGAATCCTTAGGTACGTGGCTGCGCCC"
Returns: "distinct"
"ACATTGCCAACCTCCCCACTTAGTAGGACCGCCATGTATGAATAC"
"GACCTTCCCCAACTCGTGTACGCTGAACAAAACGATAGAGA"
Returns: "distinct"
"ACCTTTATTACATACTGTGACATTGGTCGTAACTCACGCA"
"ACCTTTATTACATACTGTGACATTGGTCGAACTCACGCA"
Returns: "similar"
"GAAGTTAAACTTACTGGACAAAGCGAGTGTTTGACGACTAGAAC"
"GAAGTTAAACTTACTGGACAAGCGAGTGTTTGACGACTAGAAC"
Returns: "similar"
"GGGGCCACGCACCACAACGTGGATACCCTCGAGCACTTGTA"
"GGGCCACGCACCACAACGTGGATACCCTCGAGCACTAGTA"
Returns: "similar"
"AGGGCTTGCCCTACAGTCTCGACAAATCTGCCTTCCGTACAACACC"
"AGGGCTTGCCCTACAGTCTCGACAAATCTGCCTTCCGTACAACACA"
Returns: "similar"
"GGTCCATCCTATACAAGCAAGTCTTTTTTGTCTGCTTAAAGC"
"GGGTTCAGCCTATACAAGCAAGTCTCTTTGTCTGCTTTAAAGC"
Returns: "distinct"
"GGTGTGACCGGGGGTGTGGGGAGGGATCCAACCTAGTGGG"
"GGTGTGACCGGGGGTGCGGGGGGGATCCAACCTAGTGGG"
Returns: "similar"
"CATCGTGCTACAGACGATGCGCTGTCCCCTACTGCTCTGAT"
"CAAGATGCCGCGTAACGGGTTCGTATCAGCTGAGCCCAAAT"
Returns: "distinct"
"TCTTGCACGCTGGGGCCGCCAAATGTTATCAATCATAATT"
"TCTTGCACGCTGGGGCCGCCAAATGTTATCAATCATAATT"
Returns: "similar"
"CTTCAAGGATCCGAAAGGCCCCTCCCCTGGAGTAGGGTGCATTGGG"
"CTTCAAGGATCCGAAAGGCCCCTCCCCTCGAGTGGGTGATTGGG"
Returns: "distinct"
"CGTCGACATGGACATCCTCGTGATTCCATCAGGCATTTAGT"
"CGTCGACATGGACACCTCGTGATTCCATCAGGCATTTAGT"
Returns: "similar"
"ACATAGCTTAAAGAGTATTGGCGAAGGAAATGCCAACGACCATTG"
"ACATAGCTTAAAGAGTATTGGCGAAGGAAATGCCAACGACCAGTTG"
Returns: "similar"
"CGAGGACGTAATTTTTAGGGTGGACGCCCTTATGTCTATCT"
"CGAGGACGTAATTTATTAGGGTGGACGCCTTATGTCTATCT"
Returns: "similar"
"CTGCCGATGCGTAGTCCGAGCAGATCGGTGGATCGTGATGGGTTGG"
"CTGCCGATGCGTAGTCCGAGCAGAGCGGTGGATCGTGATGGGTTGG"
Returns: "similar"
"GAGATGGTTGCGTTTTGTGTTATGGGGGCTCGTACTGCTGATAT"
"GAGATGGTTGCGTTTTGTGTTATGGGGGCTCGTACTGCTGATTAT"
Returns: "similar"
"GGTACAAATAGCGCCTCAGTGAAAGAACTAAAAAGAGTAACAGCCGAA"
"GGTTACAAATAGCGCCTCAGTGAAAGAACTAAAAAGAGTAACAGCCGAA"
Returns: "similar"
"CAACGAGGTGTACACGACGTAAAGCGGGCTGTAATCAAACGTCGGA"
"CAACGAGGTGTACACGACGGAAAGCGGGCTGTAATAAACGTCGGA"
Returns: "similar"
"CACTAGCCGATATACCGTGACTGCTTACATTACCATCGGCGC"
"CACTAGCCGAATACCGTGACTGCTTACATTACCATCGGCGC"
Returns: "similar"
"GTTTCAATGACCGAAAATGTTTGCCGGTGAGGTGAGATGATCC"
"GTTTCAATGACCGAAAATGTTTGCCGGTGCGGTGAGATGATCC"
Returns: "similar"
"CAGGACTTGCGATTTTTTGCGATCCGTTCTGGATTAAACCGCGAAA"
"CAGGACTTGCGATTTTTTGCCGATCCGTTCTAGGATTAAACCGCGAAA"
Returns: "similar"
"AGCGTGTGCCGCCTACGCACATTAATACCCTCAATGATTTTGATTG"
"AGCGTGTGCCGCCTACGCACTTGTAATACCCTCAATGATTTTGATTG"
Returns: "similar"
"GTTACTGTCCAGAGCAAGACCTGACTTGTCTCTGCGAAGTAAACTCAAC"
"TCCCGTTTCCCACATGACGACAGTTTGGAAAGACTGCA"
Returns: "distinct"
"GCTGTGCCTACCGTCGCTGCTGACCGCTACTTTGGCGTAT"
"GCTGTGCCTACCGTCGCTGCTGACAGCTACTTTGGCGTAT"
Returns: "similar"
"TAGCATTAAGCTCCGGAATGGGACCTGCGACTGTCTAGGC"
"TAGACATAAGCTCCGGAATGGACCTGCGACTGTCTAGGC"
Returns: "distinct"
"AAGGCTGCTCGGATATCTAGTTGCCATGCACTCAAATTACAGACCCTGA"
"AAGGTGTGGGACTCAAATTCTACTTGATGAATACACATACAGGCAC"
Returns: "distinct"
"GCGGACTGCCTTTTCTGATGGAGCTACCTCAATTGGCATACG"
"GCGGACTGCCTTTTCTGATGAGCTACCTCGAATTGGCATACG"
Returns: "similar"
"ACGA"
"AGCTATT"
Returns: "distinct"
"AGCTAGCT"
"GCTAGCTA"
Returns: "similar"
"AGA"
"GAG"
Returns: "similar"
"TGCTCTGACCGTGTTGAGAATATCGGGTTTCGGGCTCATGCCCTACGATG"
"CGTAACGGACCCATACGCCCATGCGTGATGTAAGAATTGTAAAATAGGGT"
Returns: "distinct"