Problem Statement
Ribonucleic acid (RNA) is important to synthesize proteins in life activity. In this problem, we talk about messenger RNA (mRNA). We assume that an mRNA is a string consisting of 'A', 'U', 'G', and 'C'.
For an mRNA, there is a process called splicing. In this process, some parts of the mRNA is removed. The processed mRNA will be a subsequence of the original mRNA. For example, if the original mRNA is "AUUGC", the possible processed mRNAs are "UG", "AGC", "AUUGC", and so on.
The processed mRNA must be able to be translated. We consider that a processed mRNA is able to be translated if and only if it begins with "AUG".
You are given a String s which represents the original mRNA. Return the number of ways of splicing, modulo 1,000,000,007. Two ways of splicing are considered different if the sets of the removed positions are different. For example, if the original mRNA is "AUUGC", the splicing removing the first 'U' and the splicing removing the second 'U' are considered different even though the processed mRNA will be "AUGC" in both cases.
For an mRNA, there is a process called splicing. In this process, some parts of the mRNA is removed. The processed mRNA will be a subsequence of the original mRNA. For example, if the original mRNA is "AUUGC", the possible processed mRNAs are "UG", "AGC", "AUUGC", and so on.
The processed mRNA must be able to be translated. We consider that a processed mRNA is able to be translated if and only if it begins with "AUG".
You are given a String s which represents the original mRNA. Return the number of ways of splicing, modulo 1,000,000,007. Two ways of splicing are considered different if the sets of the removed positions are different. For example, if the original mRNA is "AUUGC", the splicing removing the first 'U' and the splicing removing the second 'U' are considered different even though the processed mRNA will be "AUGC" in both cases.
Definition
- Class:
- mRNASplicing
- Method:
- count
- Parameters:
- String
- Returns:
- int
- Method signature:
- int count(String s)
- (be sure your method is public)
Constraints
- s will contain between 1 and 200 characters, inclusive.
- Each character in s will be 'A', 'U', 'G' or 'C'.
Examples
"AUG"
Returns: 1
There is one way of splicing: removing nothing."AAUUGG"
Returns: 12
There are 12 ways. Those are (the dots represent removed positions): A.U.G. A.U.GG A.U..G A..UG. A..UGG A..U.G .AU.G. .AU.GG .AU..G .A.UG. .A.UGG .A.U.G"GCCGUCCUAACCGGGCCGUUCCUUU"
Returns: 0
There is no subsequence beginning with "AUG"."CAGUUGCAUGCAGUGAUCGUCAUGGCAUUGCAUGGCAUGCUAGGUCAGUGCUAGUGGCAUGCUAGCU"
Returns: 231666967
Back to all problems