import java.util.ArrayList; import java.util.HashMap; /* DNA String: A string of length L is called periodic with period p if the i-th character is equal to the (i+p)-th character for all i between 0 and L-p-1, inclusive. For example, the strings "CATCATC", "CATCAT", "ACTAC" and "ACT" are all periodic with period 3. You are given a String[] dna. Concatenate the elements of dna and return the minimum number of replacements needed to make the resulting string periodic with period less than or equal to maxPeriod. Each replacement consists of changing a single character from one letter to any other letter. Class: DNAString Method: minChanges Parameters: int, String[] Returns: int Method signature: int minChanges(int maxPeriod, String[] dna) Constraints * dna will contain between 1 and 50 elements, inclusive. * Each element of dna will contain between 1 and 50 characters, inclusive. * Each character in dna will be 'A','C','G' or 'T'. * maxPeriod will be between 1 and n, inclusive, where n is the number of characters in the concatenated string. Examples 1) input: 3, {"ATAGATA"} Returns: 1 Here, we only need one replacement to make the string periodic with period 2. Replace the 'G' with a 'T': "ATATATA". 2) input: 2, {"ACGTGCA"} Returns: 3 With 3 replacements we get the string ACACACA with period 2. 3) input: 13, {"ACGCTGACAGATA"} Returns: 0 4) input: 1, {"AAAATTTCCG"} Returns: 6 */ public class Program { private static DNAString dns; public static void main(String[] args) { dns = new DNAString(); test_minChanges_Case1(); test_minChanges_Case2(); test_minChanges_Case3(); test_minChanges_Case4(); test_minChanges_Case5(); } public static void test_minChanges_Case1() { String[] dna = new String[1]; dna[0] = "ATAGATA"; int result = dns.minChanges(3, dna); System.out.println("test_minChanges_Case1: result = " + result + ", expected 1."); } public static void test_minChanges_Case2() { String[] dna = new String[1]; dna[0] = "ACGTGCA"; int result = dns.minChanges(2, dna); System.out.println("test_minChanges_Case2: result = " + result + ", expected 3."); } public static void test_minChanges_Case3() { String[] dna = new String[1]; dna[0] = "ACGCTGACAGATA"; int result = dns.minChanges(13, dna); System.out.println("test_minChanges_Case3: result = " + result + ", expected 0."); } public static void test_minChanges_Case4() { String[] dna = new String[1]; dna[0] = "AAAATTTCCG"; int result = dns.minChanges(1, dna); System.out.println("test_minChanges_Case4: result = " + result + ", expected 6."); } public static void test_minChanges_Case5() { String[] dna = new String[5]; dna[0] = "ACGTATAGCATGACA"; dna[1] = "ACAGATATTATG"; dna[2] = "ACAGATGTAGCAGTA"; dna[3] = "ACCA"; dna[4] = "GAC"; int result = dns.minChanges(12, dna); System.out.println("test_minChanges_Case5: result = " + result + ", expected 20."); } } class DNAString { public int minChanges(int maxPeriod, String[] dna) { int min = Integer.MAX_VALUE; int k; if (dna.length == 0) return 0; // concatenate the DNS strings StringBuilder sb = new StringBuilder(dna[0]); for (k=1; k> listOfCharMap = new ArrayList>(i); for (k=0; k()); HashMap hm = listOfCharMap.get(pos); Character key = dnaString.charAt(k); if(hm.get(key) == null) hm.put(key, new Integer(1)); else { hm.put(key, hm.get(key) + 1); } if(hm.get(key) > maxCharCountPerSlot[pos]) maxCharCountPerSlot[pos] = hm.get(key); } for(k=0;k