Connection Status:
Competition Arena > SimilarDNA

SimilarDNA

SRM 809 · 2021-07-12 · by misof

SRM 809 · 2021-07-12 · by misof · Brute Force, Dynamic Programming, Greedy
Class Name: SimilarDNA
Return Type: String
Method Name: areSimilar
Arg Types: (string, string)
Problem Statement

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.

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
0)
"AAAAA"
"AACAACA"
Returns: "similar"

B can be produced from A by performing two insertions, each adding a 'C'.

1)
"AACAACA"
"AAAAA"
Returns: "similar"

The same as example 0 but in reverse: now we need two deletions.

2)
"AACAACA"
"AAGAATA"
Returns: "similar"

Two substitutions.

3)
"CGATCGAT"
"CATCGAG"
Returns: "similar"

A deletion (the first occurrence of 'G') and a substitution (the last character changes from 'T' to 'G').

4)
"CGATCGAT"
"CGATCGAT"
Returns: "similar"

Zero mutations needed.

5)
"CGATATATAGGA"
"GGATATACCATA"
Returns: "distinct"

Here we would need much more than two mutations.

Submissions are judged against all 99 archived test cases, of which 6 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class SimilarDNA with a public method string areSimilar(string A, string B) · 99 test cases · 2 s / 256 MB per case

Submitting as anonymous