Problem overview
The method countBinaryStrings receives two non-negative integers, n and k, and returns how many binary strings of length n contain no run of more than k ones in a row.
For n = 4 and k = 2 there are 16 strings of length 4. Three of them break the rule: 0111 and 1110 contain three ones in a row, and 1111 contains four. That leaves 13. The statement guarantees k <= n <= 30.
Approach: build strings one character at a time
Checking all 2^n strings works for small n, but with n up to 30 that is over a billion strings. Dynamic programming avoids it by counting strings instead of listing them.
The key observation is that to decide whether a character can be appended to a valid string, you only need to know how many ones the string currently ends with. Not the whole string. So group the valid strings by length and by that number of trailing ones: dp(i)(j) is the number of valid strings of length i that end in exactly j consecutive ones.
From a string counted in dp(i)(j) there are two ways to extend it:
- Append a 0. The run of ones is broken, so the new string, of length
i + 1, ends in zero ones. It is always valid. - Append a 1. The run grows to
j + 1ones, which is valid only ifj < k.
Every valid string of length i + 1 comes from exactly one valid string of length i plus one character, so pushing the counts forward counts each string once.
The table for n = 4, k = 2
Row i lists dp(i)(0), dp(i)(1) and dp(i)(2):
i = 0: 1 0 0
i = 1: 1 1 0
i = 2: 2 1 1
i = 3: 4 2 1
i = 4: 7 4 2
Each row's first entry is the sum of the row above, and each other entry is copied from the entry up and to the left. The last row sums to 7 + 4 + 2 = 13, the expected answer.
Step by step
- Create the table as a
valnameddpwithn + 1rows andk + 1columns, filled with zeros.Array.ofDim[Int](n + 1, k + 1)does that in one expression. The table itself never gets reassigned, only its cells change, sovalis right. - Seed the base case:
dp(0)(0) = 1. The empty string is the one valid string of length 0, and it ends in zero ones. - Loop over the lengths with
for (i <- 0 until n). The body writes into rowi + 1, soistops atn - 1and the last row written isn. - Loop over the trailing-ones counts with
for (j <- 0 to k). Usetohere, which includesk, because a valid string can end in exactlykones. - Append a 0:
dp(i + 1)(0) += dp(i)(j). The+=matters, since everyjfeeds the same cell. - Append a 1, guarded by
if (j < k):dp(i + 1)(j + 1) += dp(i)(j). The guard also keeps the indexj + 1inside the row, which has onlyk + 1cells. - Declare
var result = 0after the nested loops. Inside a loop it would reset on every pass. - Add up the last row: loop
jfrom 0 tokand doresult += dp(n)(j). A valid string of lengthnmay end in anywhere from 0 tokones. - Return
result.
The solution in Scala
class Solution {
def countBinaryStrings(n: Int, k: Int): Int = {
val dp = Array.ofDim[Int](n + 1, k + 1)
dp(0)(0) = 1
for (i <- 0 until n) {
for (j <- 0 to k) {
dp(i + 1)(0) += dp(i)(j)
if (j < k) {
dp(i + 1)(j + 1) += dp(i)(j)
}
}
}
var result = 0
for (j <- 0 to k) {
result += dp(n)(j)
}
return result
}
}
The Scala details worth a closer look:
Array.ofDim[Int](rows, cols). It allocates a two-dimensional array and fills every cell with the default for the type, which is 0 forInt. The type is given in square brackets and the sizes in parentheses.dp(i)(j) += xworks on array cells. It expands to reading the cell, adding, and writing back, even though the cell is accessed through method-call syntax.toversusuntil.0 to kincludesk;0 until nstops beforen. Both appear in this solution, each on purpose.Intis enough. Withn <= 30the largest possible answer is2^30, which is 1073741824 and fits in a 32-bitInt(maximum 2147483647). Forn = 31or more the count could reach 2147483648 and overflow silently, so a largernwould call forLong.- Explicit
return. Ending with justresulton its own line is the usual style and means the same thing.
Complexity
Time: O(n * k). The nested loops run n times k + 1 times, with constant work in each iteration, and the final sum takes O(k).
Space: O(n * k). The table has (n + 1) * (k + 1) cells. Since each row depends only on the one before it, two rows would be enough, but the lesson keeps the whole table because it is easier to follow.
Edge cases and common mistakes
k = n. Every string is allowed, so the answer is2^n. Forn = 5andk = 5the method returns 32.k = 0. No ones are allowed, so only the all-zero string counts and the answer is 1. The table has one column, and the guardj < kis never true.n = 0. The loops over lengths do not run, anddp(0)(0)is the answer: 1, the empty string.k = 1. No two ones may be adjacent. Forn = 5the answer is 13, and forn = 3it is 5.- Using
=instead of+=. Eachjwould overwritedp(i + 1)(0)instead of adding to it, and only the lastjwould be counted. - Looping
jwithuntil k. The states ending in exactlykones would never be pushed forward or summed, and the answer would come out too small. - Dropping the guard. Without
if (j < k), appending a 1 to a string withktrailing ones would write to columnk + 1and throw anArrayIndexOutOfBoundsException. - Summing every row. The answer is only the last row. Earlier rows count shorter strings.
Testing
countBinaryStrings(4, 2)gives13.countBinaryStrings(3, 1)gives5.countBinaryStrings(5, 1)gives13.countBinaryStrings(4, 0)gives1.countBinaryStrings(5, 5)gives32.countBinaryStrings(30, 30)gives1073741824.
