Java Coding Test Course, DNA Password

Problem Description

With the recent advancements in DNA analysis technology, a password system based on genetic information has been proposed. In this system, a DNA sequence of a certain length is used as a password. DNA consists of 4 nucleotides: A, T, C, and G. You need to find subsequences from a given DNA sequence that can be valid passwords. Each password must pass a validity check based on certain rules, which require a minimum and maximum occurrence of specific nucleotides.

Problem

Write a program that counts the number of valid passwords based on a given DNA string and the minimum and maximum occurrences of each nucleotide (A, T, C, G).

Input Format

• The first line contains the DNA string. (1 ≤ DNA.length ≤ 1000)
• The second line contains the minimum and maximum occurrence counts of each nucleotide (A, T, C, G) separated by spaces.

Output Format

Print the number of valid passwords.

Example

Problem-Solving Process

To solve this problem, we will follow the steps outlined below.

1. Problem Analysis

Since the password must satisfy validity conditions, we need a way to count the occurrences of each nucleotide in the subsequence. After generating all the substrings of the given DNA string, we need to check the occurrences in each substring.

2. Sliding Window Technique

Checking all substrings is inefficient due to the maximum string length of 1000. We will use a technique called sliding window. This technique maintains a combination of indices that represent a portion of the array or string, expanding or contracting as necessary to the left or right.

3. Exploring Implementation Methods

Using the sliding window, we will adjust the length of the subsequence while checking the counts of each nucleotide. During this process, we will verify if the counts meet the conditions and count valid passwords.

4. Code Writing

public class DNAPassword {
        public static void main(String[] args) {
            String dna = "AGCTTAGCTG";
            int[] minCounts = {1, 2, 1, 2}; // Minimum occurrence counts for A, T, C, G
            int[] maxCounts = {2, 3, 2, 3}; // Maximum occurrence counts for A, T, C, G
            
            System.out.println(validPasswordCount(dna, minCounts, maxCounts));
        }

        public static int validPasswordCount(String dna, int[] minCounts, int[] maxCounts) {
            int[] counts = new int[4]; // Counts for each nucleotide
            int validCount = 0;
            int left = 0;

            for (int right = 0; right < dna.length(); right++) {
                counts[getIndex(dna.charAt(right))]++;
                
                while (isValid(counts, minCounts, maxCounts)) {
                    validCount++;
                    counts[getIndex(dna.charAt(left))]--;
                    left++;
                }
            }
            return validCount;
        }

        private static int getIndex(char c) {
            switch (c) {
                case 'A': return 0;
                case 'T': return 1;
                case 'C': return 2;
                case 'G': return 3;
                default: return -1;
            }
        }

        private static boolean isValid(int[] counts, int[] minCounts, int[] maxCounts) {
            for (int i = 0; i < 4; i++) {
                if (counts[i] < minCounts[i] || counts[i] > maxCounts[i]) {
                    return false;
                }
            }
            return true;
        }
    }

5. Testing and Verification

After writing the code, experiment with the input values as shown in the example to verify that the number of valid passwords is correctly printed. Test various DNA strings and count values that meet the given conditions to check the reliability of the program.

Result Analysis

The number of valid passwords outputted as a result must actually match the answer provided in the problem. Additionally, set various test cases to confirm that the results are as expected.

Conclusion

In this course, we have covered the DNA password problem as an example of a Java coding test. I hope you have gained an understanding of how useful the sliding window technique can be in solving algorithmic problems. In the next course, we will cover more useful algorithms!