SimilarDNA | Topcoder Archive

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"
```

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.