StringWeight
SRM 586 · 2013-06-25 · by gojira_tc
SRM 586 · 2013-06-25 · by gojira_tc · Dynamic Programming, String Manipulation
Problem Statement
Problem Statement
In this problem, all strings consist of uppercase English letters only.
That is, there are 26 distinct letters.
The weight of a string S can be computed as follows: for each letter that occurs at least once in S, its leftmost and rightmost occurrences L and R are found and the weight is increased by R-L.
For example, if S="ABCACAZ", the weight of S is (5-0) + (1-1) + (4-2) + (6-6) = 7. (The leftmost occurrence of 'A' is at the index L=0, the rightmost one is at R=5, so 'A' contributes 5-0 = 5 to the weight of S. The only 'B' contributes 0, the pair of 'C's adds 2, and the only 'Z' adds 0.)
A string is S called light if no other string of the same length has a smaller weight.
You are given aint[] L.
Manao is going to choose some light strings.
The elements of L specify the lengths of these strings.
For example, if L = { 3, 42, 1 }, Manao will first choose a light string of length 3, then a light string of length 42, and finally a light string of length 1.
Then, Manao is going to concatenate all of the chosen strings, in the given order. Compute and return the smallest possible weight of a string Manao may obtain at the end.
The weight of a string S can be computed as follows: for each letter that occurs at least once in S, its leftmost and rightmost occurrences L and R are found and the weight is increased by R-L.
For example, if S="ABCACAZ", the weight of S is (5-0) + (1-1) + (4-2) + (6-6) = 7. (The leftmost occurrence of 'A' is at the index L=0, the rightmost one is at R=5, so 'A' contributes 5-0 = 5 to the weight of S. The only 'B' contributes 0, the pair of 'C's adds 2, and the only 'Z' adds 0.)
A string is S called light if no other string of the same length has a smaller weight.
You are given a
Then, Manao is going to concatenate all of the chosen strings, in the given order. Compute and return the smallest possible weight of a string Manao may obtain at the end.
Constraints
- L will contain between 1 and 50 elements, inclusive.
- Each element of L will be between 1 and 100, inclusive.
Examples
0)
{1}
Returns: 0
Every string of length 1 has weight 0.
1)
{1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1}
Returns: 1
Manao is going to concatenate 27 strings of length 1. If Manao takes 25 distinct strings and 2 equal strings and places the equal strings side by side, the weight of the resulting string will be 1.
2)
{26, 2, 2}
Returns: 8
One possible concatenation of minimum weight is "ABC...XYZ"+"YZ"+"YZ".
3)
{25, 25, 25, 25}
Returns: 1826
4)
{14, 6, 30, 2, 5, 61}
Returns: 1229
Submissions are judged against all 65 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class StringWeight with a public method int getMinimum(vector<int> L) · 65 test cases · 2 s / 256 MB per case