2672. Number of Good Binary Strings

Medium
Dynamic Programming

Description

Hints

Hint 1
If we maintain DP(i, x) where i denotes the length and x denotes the last written integer (0 or 1), then it is not hard to solve in O(maxLength * max(zeroGroup, oneGroup)).
Hint 2
Notice that from DP(i, 0) we only have a transition to DP(j, 1) where (j - i) mod oneGroup == 0 and j > i. Similarly with DP(i,1). So we can use prefix sum to optimize our DP and solve it in O(maxLength).

Similar Questions

Statistics

Acceptance
52.6%
Submissions
14,317
Accepted
7,531