RNA or DNA

Easy
0/40
1 upvote

Problem statement

Given a binary string 'S' of length 'N', determine if it represents a DNA or RNA sequence and decode its nucleotides.


The first 3 characters of 'S' indicate the type: "000" for DNA and "111" for RNA. The remaining characters, in sets of 3, represent nucleotides.


The mapping for nucleotides is as follows:

"001" -> 'A'

"010" -> 'C'

"011" -> 'G'

"100" -> 'T' (only in DNA)

"101" -> 'U' (only in RNA)


Return a string in the format "TYPE: SEQUENCE", where TYPE is "DNA" or "RNA" and SEQUENCE is the decoded string of nucleotides.


For Example : 
Let 'N' = 12, 'S' = "000001010011".
The first 3 characters "000" indicate DNA.
The subsequent 3-character sets are "001", "010", and "011".
"001" maps to 'A', "010" maps to 'C', and "011" maps to 'G' in DNA.
Therefore, the answer is "DNA: ACG".
Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line contains an integer, 'N'.
The second line contains the binary string 'S' of length 'N'.
Output Format : 
Return a string representing the type and decoded nucleotide sequence in the format "TYPE: SEQUENCE".
Note : 
You don’t need to print anything. Just implement the given function.
Constraints : 
3 <= 'N' <= 3000
'N' is a multiple of 3.
'S' contains only '0' and '1'.
The first 3 characters of 'S' are either "000" or "111".
Subsequent 3-character sets represent valid nucleotides based on the sequence type.

Time Limit: 1 sec
Sample Input 1 :
12
111001011101
Sample Output 1 :
RNA: AGU
Explanation of sample input 1 :
The length of the string is 12.
The string 'S' is "111001011101".
The first 3 characters "111" indicate an RNA sequence.
The remaining characters are processed in sets of 3: "001", "011", and "101".
For RNA, "001" maps to 'A', "011" maps to 'G', and "101" maps to 'U'.
Concatenating the type and decoded sequence gives "RNA: AGU".
Thus, the answer is "RNA: AGU".
Sample Input 2 :
12
000100001100
Sample Output 2 :
DNA: TAT
Hint

Determine the sequence type first by checking the initial 3 characters, then iterate through the rest of the string in 3-character segments to decode the nucleotides.

Approaches (1)
Implementation

Approach:

  • Check the first three characters of the input string to determine if it is a DNA or RNA sequence.
  • Initialize an empty string to store the decoded nucleotide sequence.
  • Iterate through the input string starting from the fourth character, processing it in chunks of three characters.
  • For each 3-character chunk (codon), determine the corresponding nucleotide based on the sequence type (DNA or RNA) and the defined mapping.
  • Append the decoded nucleotide to the sequence string.
  • Finally, combine the sequence type and the decoded sequence string in the specified output format.

Algorithm:

  • Initialize a string variable type.
  • Initialize an empty string variable sequence.
  • Extract the first 3 characters of S into a temporary string prefix.
  • If prefix is "000", set type to "DNA".
  • If prefix is "111", set type to "RNA".
  • Iterate using index i from 3 to N - 1, incrementing by 3 in each step:
    • Extract the substring S[i : i+3] into a temporary string codon.
    • If codon is "001", append 'A' to sequence.
    • If codon is "010", append 'C' to sequence.
    • If codon is "011", append 'G' to sequence.
    • If type is "DNA" and codon is "100", append 'T' to sequence.
    • If type is "RNA" and codon is "101", append 'U' to sequence.
  • Return type + ": " + sequence.
Time Complexity

O(N), where 'N' is the length of the input string 'S'.

We iterate through the input string 'S' once to decode the nucleotides. Thus, the overall time complexity is of the order O(N).

Space Complexity

O(1).

We use a few temporary string variables and build the output string. Excluding the output string itself from auxiliary space consideration, the space used is constant. Thus, the overall space complexity is of the order O(1).

Code Solution
(100% EXP penalty)
RNA or DNA
Full screen
Console