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 a int[] 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 int[] 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.
Definition
- Class:
- StringWeight
- Method:
- getMinimum
- Parameters:
- int[]
- Returns:
- int
- Method signature:
- int getMinimum(int[] L)
- (be sure your method is public)
Constraints
- L will contain between 1 and 50 elements, inclusive.
- Each element of L will be between 1 and 100, inclusive.
Examples
{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}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.{26, 2, 2}Returns: 8
One possible concatenation of minimum weight is "ABC...XYZ"+"YZ"+"YZ".{25, 25, 25, 25}Returns: 1826
{14, 6, 30, 2, 5, 61}Returns: 1229
Back to all problems