RequiredSubstrings
SRM 519 · 2011-05-25 · by misof
Problem Statement
In this problem we consider strings of lowercase letters ('a'-'z').
Given is a
Constraints
- words will contain between 1 and 6 elements, inclusive.
- No two elements of words will be equal.
- Each element of words will contain between 1 and 50 characters, inclusive.
- Each character in each element of words will be a lowercase letter ('a'-'z').
- C will be between 0 and the number of elements in words, inclusive.
- L will be between 1 and 50, inclusive.
{"a","aa","aaa","aaaa"}
2
3
Returns: 50
The only valid strings are strings of the form "Xaa" or "aaX", where X is one of the letters 'b'-'z'.
{"abcdefgh"}
0
7
Returns: 31810104
This answer is (26^7 modulo 1,000,000,009).
{"abcdefgh"}
1
7
Returns: 0
A string of length 7 cannot have a substring of length 8.
{"a","b","c","d"}
3
3
Returns: 24
The 24 good strings are the strings with three distinct letters, each of them in 'a'-'d'.
{"ab","bc","xy","yz"}
2
3
Returns: 2
{"aaaab","baaaa","baaaab"}
2
6
Returns: 0
impossible
{"aaaab","baaaa","baaaab"}
2
7
Returns: 1
only one: "baaaaab"
Submissions are judged against all 105 archived test cases, of which 7 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class RequiredSubstrings with a public method int solve(vector<string> words, int C, int L) · 105 test cases · 2 s / 256 MB per case