LeetCode in Kotlin
2466. Count Ways To Build Good Strings
Medium
Given the integers zero, one, low, and high, we can construct a string by starting with an empty string, and then at each step perform either of the following:
- Append the character
'0'zerotimes. - Append the character
'1'onetimes.
This can be performed any number of times.
A good string is a string constructed by the above process having a length between low and high (inclusive).
Return the number of different good strings that can be constructed satisfying these properties. Since the answer can be large, return it modulo 109 + 7.
Example 1:
Input: low = 3, high = 3, zero = 1, one = 1
Output: 8
Explanation:
One possible valid good string is “011”.
It can be constructed as follows: “” -> “0” -> “01” -> “011”.
All binary strings from “000” to “111” are good strings in this example.
Example 2:
Input: low = 2, high = 3, zero = 1, one = 2
Output: 5
Explanation: The good strings are “00”, “11”, “000”, “110”, and “011”.
Constraints:
1 <= low <= high <= 1051 <= zero, one <= low
Solution
class Solution {
fun countGoodStrings(low: Int, high: Int, zero: Int, one: Int): Int {
val dp = IntArray(high + 1)
dp[zero]++
dp[one]++
var ans = 0
for (i in 0 until high + 1) {
if (dp[i] != 0) {
if (i + zero <= high) {
dp[i + zero] += dp[i]
dp[i + zero] = dp[i + zero] % 1000000007
}
if (i + one <= high) {
dp[i + one] += dp[i]
dp[i + one] = dp[i + one] % 1000000007
}
if (i >= low) {
ans += dp[i]
ans = ans % 1000000007
}
}
}
return ans
}
}