StringWeightDiv2
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.)
You are given aint L.
Consider all strings of length L.
Compute the weight of each of these strings.
The strings with the minimum weight among all of them are called light.
Your task is to count the number of light strings of length L.
Since this count may be very large, return it modulo 1,000,000,009.
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.)
You are given a
Constraints
- L will be between 1 and 1000, inclusive.
Examples
0)
1 Returns: 26
Any string of length 1 has weight equal to 0.
1)
2 Returns: 650
We can divide strings of length 2 into two classes: the strings with distinct first and second letter, and the strings with two equal letters. The strings composed of two equal letters have weight 1. All the other strings have weight 0. Thus, the number of strings of minimum weight is 26*26-26=650.
2)
50 Returns: 488801539
3)
3 Returns: 15600
4)
4 Returns: 358800
Submissions are judged against all 24 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class StringWeightDiv2 with a public method int countMinimums(int L) · 24 test cases · 2 s / 256 MB per case