TopBiologist
SRM 682 · 2016-01-04 · by zxqfl
SRM 682 · 2016-01-04 · by zxqfl · String Manipulation
Problem Statement
Problem Statement
For the purposes of this problem, a DNA sequence is a string consisting of the letters A, C, G, and T.
You have been hired to help researchers at TopBiologist uncover the secrets of the human genome. The researchers have identified a DNA sequence, which is given to you in theString sequence. They have asked you to write a program which finds the shortest DNA sequence that is not contained in sequence.
For example, if sequence is the string "AGGTCTA", then one possible answer would be the string "AC". Other solutions, such as "CC", would also be accepted. "AG" would be an invalid answer because "AG" is contained in sequence. "AAA" would also be invalid: although it isn't contained in sequence, it is 3 characters long, and there are better answers which are only 2 characters long.
You are not really sure how this could possibly help anyone's research, but it's not your job to question TopBiologist. Find and return the shortest DNA sequence which is not contained in sequence. If there are multiple possible answers, you may return any of them.
You have been hired to help researchers at TopBiologist uncover the secrets of the human genome. The researchers have identified a DNA sequence, which is given to you in the
For example, if sequence is the string "AGGTCTA", then one possible answer would be the string "AC". Other solutions, such as "CC", would also be accepted. "AG" would be an invalid answer because "AG" is contained in sequence. "AAA" would also be invalid: although it isn't contained in sequence, it is 3 characters long, and there are better answers which are only 2 characters long.
You are not really sure how this could possibly help anyone's research, but it's not your job to question TopBiologist. Find and return the shortest DNA sequence which is not contained in sequence. If there are multiple possible answers, you may return any of them.
Notes
- Formally, we say that sequence X is contained in sequence Y if we can obtain X by erasing some (possibly none) elements from the beginning and from the end of Y. For example, "AB" is contained in "ABC", but "AC" is not contained in "ABC".
Constraints
- sequence will contain between 1 and 2000 characters, inclusive.
- Each character of sequence will be A, C, G, or T.
Examples
0)
"AGGTCTA" Returns: "AC"
This is the example from the problem statement. Any of the following answers will be accepted: "AA", "AC", "AT", "CA", "CC", "CG", "GA", "GC", "TG", and "TT".
1)
"AGACGACGGAGAACGA" Returns: "T"
2)
"A" Returns: "C"
3)
"AAGATACACCGGCTTCGTG" Returns: "CAT"
4)
"ACATAGATACAT" Returns: "AA"
Submissions are judged against all 42 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class TopBiologist with a public method string findShortestNewSequence(string sequence) · 42 test cases · 2 s / 256 MB per case