Problem Statement
This problem is vaguely motivated by an encounter with some kids who were learning to write cursive.
One of the commonly used techniques when teaching writing is taking dictation: the teacher says some words and the kids write them down. (This applies mostly to languages with shallow orthography, i.e., ones where there is a straightforward correspondence between sounds and letters, and thus determining the right spelling of the teacher's words isn't a separate challenge.)
When preparing a good set of words the teachers can dictate, one needs to be careful about not overrepresenting a specific character. For example, if all words in the set contain the letter 'f', a kid who doesn't know how to write 'f' correctly will have a mistake in all of them. This is unfortunate, because some bad teachers will then simply mark all the words as wrong.
The problem that follows is a counting problem focusing on the extremal case of the situation described above.
Given a set S of strings, an omnipresent letter is a letter that appears one or more times in each string in S. I.e., if you don't know how to write a letter that is omnipresent in S, you will write all words in S incorrectly.
The danger level DL(S) of the set S is the number of its distinct omnipresent letters.
For example, the set {"cat", "dog"} has danger level 0, the set {"cat", "carrot", "banana"} has danger level 1 because 'a' is omnipresent, and the one-element set {"carrot"} has danger level 5.
You are given
In this problem, valid words are precisely the strings with the following properties:
- Each character is one of the first N lowercase English letters.
- Their length is between 1 and L, inclusive.
- In lexicographic order they lie in the half-open interval [ A, B ). That is, they are greater than or equal to A and also striclty smaller than B.
We are going to select exactly D distinct valid words for the dictation.
Let M = min( N, L ). Clearly, any set of words we'll select will have danger level between 0 and M, inclusive.
For each i, let W(i) denote the number of ways in which we can have a dictation with danger level i.
Return a
Definition
- Class:
- LearningCursive
- Method:
- count
- Parameters:
- int, int, int, String, String
- Returns:
- int[]
- Method signature:
- int[] count(int N, int L, int D, String A, String B)
- (be sure your method is public)
Constraints
- N will be between 1 and 12, inclusive.
- L will be between 1 and 12, inclusive.
- D will be between 1 and 12, inclusive.
- A will contain between 1 and L characters, inclusive.
- B will contain between 1 and L characters, inclusive.
- Each character in A will be one of the first N lowercase English letters.
- Each character in B will be one of the first N lowercase English letters.
- A will be lexicographically smaller than B.
- A and B will be such that the number of valid words won't exceed 10^9.
Examples
12
1
1
"b"
"e"
Returns: {0, 3 }
The valid words are "b", "c", and "d". The 1-element sets we can select for dictation are {"b"}, {"c"}, and {"d"}. Each of them has danger level 1.
5
3
1
"ab"
"ed"
Returns: {0, 10, 69, 57 }
These are all the valid words, in lexicographic order: "ab", "aba", "abb", "abc", "abd", "abe", "ac", "aca", "acb", "acc", "acd", "ace", "ad", "ada", "adb", "adc", "add", "ade", "ae", "aea", "aeb", "aec", "aed", "aee", "b", "ba", "baa", "bab", "bac", "bad", "bae", "bb", "bba", "bbb", "bbc", "bbd", "bbe", "bc", "bca", "bcb", "bcc", "bcd", "bce", "bd", "bda", "bdb", "bdc", "bdd", "bde", "be", "bea", "beb", "bec", "bed", "bee", "c", "ca", "caa", "cab", "cac", "cad", "cae", "cb", "cba", "cbb", "cbc", "cbd", "cbe", "cc", "cca", "ccb", "ccc", "ccd", "cce", "cd", "cda", "cdb", "cdc", "cdd", "cde", "ce", "cea", "ceb", "cec", "ced", "cee", "d", "da", "daa", "dab", "dac", "dad", "dae", "db", "dba", "dbb", "dbc", "dbd", "dbe", "dc", "dca", "dcb", "dcc", "dcd", "dce", "dd", "dda", "ddb", "ddc", "ddd", "dde", "de", "dea", "deb", "dec", "ded", "dee", "e", "ea", "eaa", "eab", "eac", "ead", "eae", "eb", "eba", "ebb", "ebc", "ebd", "ebe", "ec", "eca", "ecb", "ecc", "ecd", "ece". We are selecting a single word. Its danger level is simply the number of distinct characters it contains. Thus, there are no sets with danger level 0: each word contains some letters. The 10 sets with danger level 1 are {"b"}, {"bb"}, {"bbb"}, {"c"}, {"cc"}, {"ccc"}, {"d"}, {"dd"}, {"ddd"}, and {"e"}.
5
3
2
"ab"
"ed"
Returns: {1769, 4904, 2372, 135 }
The same set of valid words but now we are selecting a two-word set for dictation. Now we have some sets with danger level 0, for example the set {"abb", "e"}. One of the sets with danger level 3 is {"ace", "cae"}. One of the sets with danger level 1 is {"ae", "daa"}.
12
7
5
"cabbaga"
"cabbage"
Returns: {0, 0, 0, 0, 0, 0, 0, 0 }
There are only four valid words. Hence, there is no way to select a five-word set. Note that the correct return value has exactly 8 zeros.
2
10
3
"a"
"bbbbbbbbbb"
Returns: {183105, 39139485, 383960593 }
There are 2045 valid words. Almost all of them (2026, to be exact) contain both at least one 'a' and at least one 'b'. The dictations with danger level 2 are precisely the sets of three such words, so there are binomial(2026,3) = 1383960600 of them. This, modulo 10^9 + 7, is the last number in the return value.
12
12
12
"dllla"
"dlllllc"
Returns: {0, 0, 664541784, 877220979, 238907414, 607827828, 161030015, 328644456, 691002605, 34621674, 167995607, 0, 0 }
4
5
3
"cbadd"
"dd"
Returns: {930623, 6499470, 8992888, 2908450, 156849 }
5
12
9
"abcac"
"eede"
Returns: {829360855, 826134822, 806770390, 911707177, 903976061, 344148754 }
12
8
10
"aal"
"laa"
Returns: {653910265, 976782814, 532201598, 973333725, 991106202, 998764641, 838750029, 944268420, 539806985 }
1
12
3
"aa"
"aaaaaa"
Returns: {0, 4 }
6
2
7
"ec"
"ed"
Returns: {0, 0, 0 }
7
10
1
"dbaecf"
"eceegb"
Returns: {0, 10, 7099, 493231, 6396705, 22301226, 22834464, 5682502 }
4
12
1
"cac"
"dcabcbdadc"
Returns: {0, 12, 15320, 1042046, 6773110 }
11
5
4
"efija"
"ejge"
Returns: {0, 218242490, 893583753, 208992821, 570116579, 87725 }
12
9
4
"lcchdcb"
"ljf"
Returns: {0, 551837824, 506517701, 258456298, 715909389, 165583075, 722017319, 241750989, 246802379, 852887602 }
9
7
2
"c"
"ih"
Returns: {896576391, 754019791, 52842322, 314832592, 662867564, 638511291, 721227873, 269390700 }
4
8
9
"baaddada"
"dabcc"
Returns: {510989980, 759119144, 432234769, 777357958, 569480208 }
3
8
1
"bbcba"
"cc"
Returns: {0, 1, 442, 3078 }
7
6
1
"ega"
"fgcc"
Returns: {0, 6, 342, 3741, 9522, 6132, 780 }
4
5
4
"daadd"
"dccac"
Returns: {0, 20250446, 30932312, 8102572, 341055 }
2
3
7
"ab"
"bab"
Returns: {0, 0, 0 }
1
3
10
"a"
"aa"
Returns: {0, 0 }
4
8
3
"abadadd"
"cadaadda"
Returns: {8261894, 397555059, 986998643, 969583950, 323210381 }
10
3
11
"fgd"
"gb"
Returns: {243557676, 160169650, 1094, 0 }
3
12
8
"acbcaccb"
"ba"
Returns: {346018300, 478620640, 583432632, 674248903 }
3
10
2
"aaac"
"caa"
Returns: {10729, 4912851, 198455784, 413178859 }
2
3
10
"a"
"ab"
Returns: {0, 0, 0 }
12
11
7
"fiigiejab"
"fiiibjljdba"
Returns: {0, 0, 257903202, 218168778, 472316572, 653184795, 283278730, 506064412, 637914265, 157566103, 962961082, 0 }
5
8
3
"dccbdbcd"
"dcdedba"
Returns: {0, 0, 882380955, 336970379, 768212072, 351988484 }
6
8
10
"ccadfdb"
"ce"
Returns: {0, 803614470, 703250468, 536673770, 19109747, 530413902, 234194365 }
2
12
11
"baaababbba"
"bbbbba"
Returns: {0, 82051251, 465037064 }
2
12
5
"baabaa"
"bbbaaba"
Returns: {0, 627808472, 756645811 }
5
1
3
"c"
"e"
Returns: {0, 0 }
4
10
6
"ad"
"baaaabdbbb"
Returns: {116125532, 439642902, 499556551, 595284464, 920403563 }
3
10
11
"ac"
"cccab"
Returns: {364701132, 823020444, 879820919, 902650171 }
5
7
2
"bbdeac"
"bdabae"
Returns: {0, 165411, 2390630, 5874673, 3651174, 480690 }
2
9
11
"b"
"bbbbab"
Returns: {0, 937664986, 799388461 }
5
4
2
"b"
"c"
Returns: {0, 4040, 6220, 1770, 60 }
6
2
5
"af"
"b"
Returns: {0, 0, 0 }
1
9
4
"a"
"aa"
Returns: {0, 0 }
12
6
3
"fj"
"ia"
Returns: {982528318, 737850824, 212821636, 604638181, 110115185, 875641263, 768053328 }
4
11
1
"acac"
"bb"
Returns: {0, 1, 2812, 161676, 840395 }
8
10
11
"bdfecachh"
"d"
Returns: {953556768, 453280698, 140134070, 660625111, 105306396, 249580992, 487291074, 281146440, 610222651 }
10
1
7
"e"
"i"
Returns: {0, 0 }
7
1
10
"d"
"e"
Returns: {0, 0 }
6
7
7
"cadaee"
"eabf"
Returns: {201648325, 489033258, 567894469, 808708174, 985549294, 860537101, 271017667 }
7
5
4
"b"
"d"
Returns: {817067938, 234131482, 385809214, 351414347, 909264236, 2052060 }
1
5
5
"aa"
"aaaa"
Returns: {0, 0 }
6
12
2
"de"
"fedeecc"
Returns: {885714150, 856689332, 277128696, 78739016, 431269862, 902440957, 405883917 }
8
10
2
"bgacadfb"
"e"
Returns: {687689100, 498608101, 168148299, 428545244, 845958727, 629588474, 100307313, 820424917, 928062366 }
9
4
5
"ag"
"iehh"
Returns: {670771595, 395791733, 797909186, 742994476, 3137682 }
3
10
1
"aabbbccbbc"
"caaacbab"
Returns: {0, 11, 3401, 51418 }
2
8
2
"ababa"
"bbab"
Returns: {0, 505, 31626 }
6
10
6
"a"
"eebfedfd"
Returns: {549812707, 719839813, 917599137, 697491141, 455713331, 620566093, 682071706 }
1
11
9
"aaaaa"
"aaaaaaaaa"
Returns: {0, 0 }
6
11
11
"bdfceabfee"
"eff"
Returns: {313089859, 768114874, 639099327, 743249430, 727640163, 698599461, 931272820 }
12
7
4
"fcflb"
"lcedg"
Returns: {888486050, 183454572, 621043871, 408372913, 27914666, 496619517, 941599952, 400904564 }
1
12
3
"aaaaaaaa"
"aaaaaaaaaaaa"
Returns: {0, 4 }
2
6
11
"b"
"bb"
Returns: {0, 44352165, 84672315 }
10
10
6
"g"
"ggegjd"
Returns: {0, 39202214, 402519616, 776398575, 609838327, 854624514, 898178936, 504121324, 920081544, 734543372, 369727287 }