TopCoder problem "DNAString" used in SRM 396 (Division I Level One , Division II Level Two)



Problem Statement

    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.
 

Definition

    
Class:DNAString
Method:minChanges
Parameters:int, String[]
Returns:int
Method signature:int minChanges(int maxPeriod, String[] dna)
(be sure your method is public)
    
 

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

0)
    
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".
1)
    
2
{"ACGTGCA"}
Returns: 3
With 3 replacements we get the string ACACACA with period 2.
2)
    
13
{"ACGCTGACAGATA"}
Returns: 0
Here there is no need to change anything since our string already has period 13.
3)
    
1
{"AAAATTTCCG"}
Returns: 6
The best way to do this is to replace all non-'A' characters with 'A's.
4)
    
12
{"ACGTATAGCATGACA","ACAGATATTATG","ACAGATGTAGCAGTA","ACCA","GAC"}
Returns: 20

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=8584

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=12168&pm=8584

Writer:

asal1

Testers:

PabloGilberto , Olexiy , Andrew_Lazarev , ivan_metelsky

Problem categories:

Greedy, Simple Search, Iteration