Problem Statement
In this problem we will use strings over the alphabet ACGT.
For simplicity, we will call them chromosomes.
We will consider a special genetic recombination called a chromosomal crossover. At the beginning of such a recombination we have two strings of the same length: X and Y. During the chromosomal crossover X and Y will swap their prefixes of the same length. Formally, there will be an integer k between 1 and the length of X, inclusive, with the following property: X will change into Y[0..k-1] + X[k..], and Y will change into X[0..k-1] + Y[k..]. For example, a chromosomal crossover with k = 3 will change the pair "CCCCC", "GGGGG" into the pair "GGGCC", "CCCGG".
Let lcs(X,Y) denote the length of the longest common substring of the strings X and Y. Note that the substring must be contiguous. For example, lcs("CAAA","AAAG") = 3, and lcs("CAC","CTC") = 1. For chromosomes X and Y the value lcs(X,Y) is called their similarity value.
You are given two chromosomes: two equally-long Strings A and B. You may perform an arbitrary number of chromosomal crossovers, one after another. Compute and return the largest similarity value that can be obtained.
We will consider a special genetic recombination called a chromosomal crossover. At the beginning of such a recombination we have two strings of the same length: X and Y. During the chromosomal crossover X and Y will swap their prefixes of the same length. Formally, there will be an integer k between 1 and the length of X, inclusive, with the following property: X will change into Y[0..k-1] + X[k..], and Y will change into X[0..k-1] + Y[k..]. For example, a chromosomal crossover with k = 3 will change the pair "CCCCC", "GGGGG" into the pair "GGGCC", "CCCGG".
Let lcs(X,Y) denote the length of the longest common substring of the strings X and Y. Note that the substring must be contiguous. For example, lcs("CAAA","AAAG") = 3, and lcs("CAC","CTC") = 1. For chromosomes X and Y the value lcs(X,Y) is called their similarity value.
You are given two chromosomes: two equally-long Strings A and B. You may perform an arbitrary number of chromosomal crossovers, one after another. Compute and return the largest similarity value that can be obtained.
Definition
- Class:
- ChromosomalCrossover
- Method:
- maximalLength
- Parameters:
- String, String
- Returns:
- int
- Method signature:
- int maximalLength(String A, String B)
- (be sure your method is public)
Constraints
- A will contain between 1 and 50 elements, inclusive.
- A and B will contain the same number of elements.
- Each character in A will be one of {'A', 'T', 'C', 'G'}.
- Each character in B will be one of {'A', 'T', 'C', 'G'}.
Examples
"AAAAAA"
"TCGTCG"
Returns: 3
One optimal solution is to do just a single crossover with k = 3. This produces the chromosomes "TCGAAA" and "AAATCG". Their similarity value is 3 because of the common substring "AAA"."AAA"
"CCC"
Returns: 2
This time we need to do it twice, first we swap prefix of length 2: ("AAA", "CCC") -> ("CCA", "AAC"). Then we swap prefix of length 1: ("CCA", "AAC") -> ("ACA", "CAC")."ATCGATCGATCG"
"ATCGATCGATCG"
Returns: 12
This time we don't need to do anything."AAAAATTTTTCCCCCGGGGG"
"ACTTCATGTGCTAGCTGTAG"
Returns: 4
"A"
"G"
Returns: 0
Back to all problems