DNAString
SRM 396 · 2008-04-03 · by asal1
SRM 396 · 2008-04-03 · by asal1 · Greedy, Simple Search, Iteration
Problem Statement
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 aString[] 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.
You are given a
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
Submissions are judged against all 87 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class DNAString with a public method int minChanges(int maxPeriod, vector<string> dna) · 87 test cases · 2 s / 256 MB per case