Recently, a biologist found themselves in a situation where they needed to create a specific password using DNA sequences. This DNA sequence consists of four types of nucleotides: A, C, G, and T. The password is generated from a combination of A, C, G, and T selected from the given DNA sequence.<\/p>\n
Write a program to find the substring of length K among all substrings of the given string S where the frequency of each nucleotide is minimized, and determine the number of valid passwords among them. If all frequencies are the same, select the smallest lexicographic string among those with the minimum frequency. The length of the substring must be less than or equal to the given string.<\/p>\n
Print the number of valid passwords and the smallest lexicographic password among them.<\/p>\n
To solve this problem, we will use the Sliding Window technique. This method allows us to move through substrings of a specific length K while counting the frequency of each character (A, C, G, T) to solve the problem.<\/p>\n
Below is a C++ code example to solve this problem:<\/p>\n
\n #include <iostream>\n #include <string>\n #include <unordered_map>\n #include <vector>\n #include <algorithm>\n\n using namespace std;\n\n int main() {\n int N, K;\n string S;\n cin >> N >> K;\n cin >> S;\n\n unordered_map freq;\n for (int i = 0; i < K; i++) {\n freq[S[i]]++;\n }\n\n \/\/ Initial result setup\n int min_freq = INT_MAX;\n vector passwords;\n\n \/\/ Sliding window to check all K-length substrings\n for (int i = 0; i <= N - K; i++) {\n if (i > 0) {\n freq[S[i - 1]]--;\n freq[S[i + K - 1]]++;\n }\n\n \/\/ Finding the smallest frequency\n int cur_min = INT_MAX;\n for (const auto &entry : freq) {\n cur_min = min(cur_min, entry.second);\n }\n\n \/\/ Adding valid password\n if (cur_min <= (K \/ 4)) { \/\/ Frequency of all nucleotides is less than or equal to K\/4\n passwords.push_back(S.substr(i, K));\n }\n }\n\n \/\/ Finding the smallest lexicographic password\n sort(passwords.begin(), passwords.end());\n string smallest_password = (passwords.empty() ? \"\" : passwords[0]);\n \n \/\/ Output result\n cout << passwords.size() << \" \" << smallest_password << endl;\n\n return 0;\n }\n <\/string><\/char,><\/pre>\n4. Code Explanation<\/h2>\n
The above code works as follows:<\/p>\n
\n- First, the DNA string and its length, along with the length K of the substring, are input.<\/li>\n
- An
unordered_map<\/code> is used to count the frequency of the first K characters.<\/li>\n- The Sliding Window technique is used to move through each K-length substring, modifying the frequency.<\/li>\n
- The minimum frequency is calculated for each substring, adding to the valid password list only when conditions are met.<\/li>\n
- Finally, the valid password list is sorted to find the smallest lexicographic password.<\/li>\n<\/ul>\n
5. Test Cases<\/h2>\n
Now, let’s look at some test cases to solve this problem:<\/p>\n
Test Case 1<\/h3>\n\n Input:\n 8 4\n ACGTTGCA\n\n Output:\n 1 ACGT\n <\/pre>\nTest Case 2<\/h3>\n\n Input:\n 12 5\n ACGTTACGATC\n\n Output:\n 3 ACCTA ACTAC TCGAT\n <\/pre>\nTest Case 3<\/h3>\n\n Input:\n 6 3\n ACGTAC\n\n Output:\n 2 ACG ACT\n <\/pre>\n6. Conclusion<\/h2>\n
In this tutorial, we learned an algorithm utilizing the sliding window technique through the DNA password problem. This technique can be very useful in solving string-related problems and can be applied to various modified problems. It serves as a solid foundation that can be beneficial in coding tests.<\/p>\n
<\/body><\/p>\n","protected":false},"excerpt":{"rendered":"