Many people are solving algorithm problems to prepare for coding tests. In this course, we will explore the DNA password problem and explain step by step how to solve it.<\/p>\n
The DNA password consists of a specific pattern of combinations. The problem is to find how many substrings from the given DNA string can become passwords. Here are the details of the problem.<\/p>\n
\n From the given DNA string, count the number of distinct substrings that contain only the characters “””ACGT””” and are of length K or more.\n <\/p><\/blockquote>\n
Input<\/h3>\n
\n
- The first line contains the DNA string. (1 \u2264 string length \u2264 1000)<\/li>\n
- The second line contains the value of K. (1 \u2264 K \u2264 100)<\/li>\n<\/ul>\n
Output<\/h3>\n
Output the total number of distinct substrings.<\/p>\n
Problem Solving Process<\/h2>\n
To solve this problem efficiently, we will follow these steps:<\/p>\n
Step 1: Generate Substrings<\/h3>\n
Generate all substrings of length K or more from the given DNA string. To do this, we will iterate over the starting indexes of the string and extract substrings of length K or more from each starting index.<\/p>\n
Step 2: Store Unique Substrings<\/h3>\n
Store the generated substrings in a set. Since a set does not allow duplicates, only distinct substrings will be stored. We can utilize the
set<\/code> data type in this process.<\/p>\nStep 3: Output Result<\/h3>\n
Finally, we count the number of substrings stored in the set and output the result. Now let’s convert these processes into code.<\/p>\n
Python Code<\/h2>\n
\ndef count_unique_dna_substrings(dna: str, k: int) -> int:\n unique_substrings = set() # Set to store substrings\n n = len(dna)\n\n # Extract substrings for all starting positions in the string\n for start in range(n):\n for end in range(start + k, n + 1): # Only consider lengths >= K\n substring = dna[start:end]\n unique_substrings.add(substring)\n\n return len(unique_substrings) # Return the count of unique substrings\n\n# Input\nif __name__ == \"__main__\":\n dna_string = input(\"Please enter the DNA string: \")\n k_value = int(input(\"Please enter the length K: \"))\n \n # Calculate and print the number of unique substrings\n result = count_unique_dna_substrings(dna_string, k_value)\n print(f\"The number of distinct substrings is: {result}\")\n <\/code><\/pre>\nCode Explanation<\/h2>\n
The function
count_unique_dna_substrings<\/code> used in the above code takes two parameters: thedna<\/code> string and thek<\/code> value. This function first creates an empty set to prepare to store substrings. It then extracts substrings through a loop that will be explained in the next step.<\/p>\nLoop Explanation<\/h3>\n
The first loop iterates over the starting index (
start<\/code>) of the DNA string. The second loop extracts substrings of length K or more starting from thestart<\/code> index, thus determining theend<\/code> index. Each substring is added to the set, only storing distinct cases.<\/p>\nExample for Understanding<\/h3>\n
For example, if the input DNA string is
ACGTACGT<\/code> and the value of K is 2, the possible substrings that can be generated are as follows:<\/p>\n\n
- AC, ACG, ACGT, ACGTA, ACGTAC, ACGTACGT<\/li>\n
- CG, CGT, CGTA, CGTAC, CGTACG<\/li>\n
- GT, GTA, GTAC, GTACG<\/li>\n
- TA, TAC, TACG<\/li>\n
- AC, ACG, ACGT<\/li>\n<\/ul>\n
In total, there will be 14 distinct substrings.<\/p>\n
Performance Considerations<\/h2>\n
The above code checks all substring lengths for every starting index, resulting in a worst-case time complexity of O(n^3). Performance issues may occur when the string length reaches 1000. To enhance performance in extreme cases, we can consider applying the
Sliding Window<\/code> technique.<\/p>\nApplication of Sliding Window Technique<\/h3>\n
Using the Sliding Window technique allows us to easily calculate the number of substrings with length >= K in a single pass. It means storing information about the length of the string during one pass to facilitate exploration. This technique can reduce time complexity to O(n^2) or O(n).<\/p>\n
Conclusion<\/h3>\n
In this course, we learned how to handle substrings of a string and resolve duplication issues using sets through the DNA password problem. Such problems frequently appear in coding tests, so it is recommended to be well-versed in basic string handling methods. In the next course, we will cover another useful algorithm problem.<\/p>\n