BadSubstring
SRM 178 · 2004-01-07 · by brett1479
SRM 178 · 2004-01-07 · by brett1479 · Dynamic Programming
Problem Statement
Problem Statement
Return how many strings containing length characters do not have the substring (quotes for clarity) "ab". The only characters allowed in the strings are 'a', 'b', and 'c'. A substring is any contiguous portion of a string. A substring may be empty, or the entire string.
Constraints
- length will be between 0 and 44 inclusive.
Examples
0)
0 Returns: 1
The only string of length 0 is the empty string, and it doesn't have "ab" as a substring.
1)
3 Returns: 21
There are 3*3*3=27 possible strings of length 3. 3 begin with ab, and 3 end with ab. The remaining 21 are all good.
2)
29 Returns: 1548008755920
3)
0 Returns: 1
4)
1 Returns: 3
Submissions are judged against all 56 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class BadSubstring with a public method long long howMany(int length) · 56 test cases · 2 s / 256 MB per case