Problem Statement
Let C(Haystack, Needle) be the number of different (possibly overlapping) occurrences of the string Needle in the string Haystack as a contiguous substring.
For example, C("ababababa", "aba") = 4, C("cat", "catastrophy") = 0, and C("canyoudancecancan", "can") = 3.
Given is a string S of lowercase English letters and an int L.
Let Cmax be the largest possible number of times S may occur in a string of length L. In other words, Cmax is the maximum value of C(T, S) taken over all strings T of length L.
Count all strings T made of exactly L lowercase English letters such that C(T, S) = Cmax. Return their count modulo 10^9 + 7.
Definition
- Class:
- MostSubstrings
- Method:
- count
- Parameters:
- String, int
- Returns:
- int
- Method signature:
- int count(String S, int L)
- (be sure your method is public)
Constraints
- S will have between 1 and 100 characters, inclusive.
- Each character of S will be a lowercase English letter.
- L will be between 1 and 1000, inclusive.
Examples
"helloworld"
7
Returns: 31810120
Each of the 26^7 possible strings of length 7 contains 0 occurrences of the string "helloworld", so each of them is optimal. The return value is (26^7 modulo (10^9 + 7))."aaaa"
13
Returns: 1
The only optimal string is "aaaaaaaaaaaaa" (13 'a's)."dogecoin"
17
Returns: 78
The optimal answers are strings of the form "Xdogecoindogecoin", "dogecoinXdogecoin", and "dogecoindogecoinX", where X can be any single letter."decode"
11
Returns: 52
Now the optimal solutions are strings of the form "Xdecodecode" and "decodecodeX".