d) needs a bit elaboration.
(i) If the question is about a run of exactly 4 $0$'s (though possibly a longer run elsewhere), we can count like this:
There are $2^5$ strings starting with $00001$.
There are $2^5$ strings ending with $10000$.
For $0\le k\le 4$ there are $2^4$ strings $\alpha100001\beta$, where $\alpha$ is $k$ digits and $\beta$ is $4-k$ digits long. Note that we need the "sentinel" $1$s to prevent the block from being longer than 4.
That gives $2^5+2^5+5\cdot2^4=144$ strings.
However, $0000100001$, $0000110000$, $1000010000$ are counted twice, thus the answer is: 141.
Note that e.g. $0000100000$ is counted even though it has (also) a run of 5 0's.
(ii) If the question is about a run of at least 4 $0$'s, we can do this:
There are $2^6$ strings beginning with $0000$, i.e. with the block starting at the first digit.
For $2\le k\le 6$, there are $2^5$ strings of the form $\alpha10000\beta$ with $\alpha$ of length $k-1$ and $\beta$ of length $6-k$, i.e. with the block starting at the $k$th digit.
This give $2^6+5\cdot2^5=224$ strings.
However, we counted solutions with two blocks twice, namely $0000100001$, $0000110000$, $1000010000$, $0000100000$, $0000010000$. (Fortunately, there is not much room for two blocks).
Thus the answer is: 219.
Note: You could model the situation with generating functions. We start with some preliminary considerations, introducing a symbolic method for combinatorial structures from which we can easily derive corresponding generating functions.
Problem: Let's consider binary strings containing $0s$ and $1s$. We are looking for the number of strings with length $n$, having at most $k_1$ consecutive $0$s and $k_2$ consecutive $1$s. We want to count the strings with $x$ $0$s and $y$ $1$s.
We build them starting with simpler patterns. Let $$\text{SEQ}(1)=\{\varepsilon,1,11,111,\ldots\}$$ denote all strings containing only $1$s with length $\geq0$. The empty string is denoted with $\varepsilon$. The corresponding generating function is $$w^0+w^1+w^2+\ldots=\frac{1}{1-w},$$ with the exponent of $w^n$ marking the length $n$ of a string of $1s$ and the coefficient of $w^n$ marking the number of strings of length $n$. Similarly, we define $\text{SEQ}(0)=\{\varepsilon,0,00,000,\ldots\}$.
Let $\text{SEQ}^{\leq k}(1)$ be the set of all strings of $1$s with length $\leq k$. The generating function for $\text{SEQ}^{\leq k}(1)$ is $$1+w+w^2+\ldots+w^{k}=\frac{1-w^{k+1}}{1-w}$$
Simplified problem: First we consider the simplified variant:
$$k_1=k_2=1,$$
namely strings having runs of $0$s and $1$s of maximum length $1$.
How could we describe all these strings? We may have a leading $1$. So, we start with zero or one $1$s. Formally:
$$\text{SEQ}^{\leq 1}(1)=\{\varepsilon,1\}$$
with generating function
$$1+w$$
Then we may have zero or more groups, each group containing a $0$ followed by a $1$. Formally:
$$\text{SEQ}(01)=\{\varepsilon,01,0101,010101,\ldots\}$$
with generating function $$1+uw+(uw)^2\ldots=\frac{1}{1-uw}$$ Observe, that since we want to count $x$ $0$s and $y$ $1$s separately, we encode them using a bivariate generating function with $u$ indicating the amount of $0$s and $w$ indicating the amount of $1$s. The strings may finish with zero or one $0$, formally $\text{SEQ}^{\leq 1}(0)$ with generating function $1+u$.
We conclude: The binary strings having runs of $0$s and $1$s of maximum length $1$ are modelled by
\begin{align*}
\text{SEQ}^{\leq 1}(1)\text{SEQ}(01)\text{SEQ}^{\leq 1}(0)\tag{1}
\end{align*}
with generating function
\begin{align*}
\frac{(1+u)(1+w)}{1-uw}\tag{2}
\end{align*}
General Problem: Now we consider the symbolic expression for the general problem. Since we have to consider runs of at most $k_1$ $0$s and runs of at most $k_2$ $1s$ we have to substitute the outer occurrences $0$ and $1$ by up to $k_1$ $0$s resp. $k_2$ $1$s and the inner $0$s and $1$s enlarge by up to $k-1$ $0$s resp. $1$s. So, we get
\begin{align*}
\text{SEQ}^{\leq k_2}(1)\text{SEQ}\left(0\text{SEQ}^{\leq k_1-1}(0)1\text{SEQ}^{\leq k_2-1}(1)\right)\text{SEQ}^{\leq k_1}(0)\tag{3}
\end{align*}
with the corresponding bivariate generating function $G(u,w)$
\begin{align*}
G(u,w)=\frac{\left(\frac{1-u^{k_1+1}}{1-u}\right)\left(\frac{1-w^{k_2+1}}{1-w}\right)}
{1-\left(u\frac{1-u^{k_1}}{1-u}\right)\left(w\frac{1-w^{k_2}}{1-w}\right)}\tag{4}
\end{align*}
In order to simplify calculations we introduce:
\begin{align*}
H_k(z)=\frac{1-z^k}{1-z}
\end{align*}
We use the coefficient of operator $[z^n]$ to denote the coefficient of $z^n$ of the corresponding generating function and so we can conclude:
Result: The number of $x$ $0$s and $y$ $1$s of strings of length $n=x+y$ containing runs of at most $k_1$ $0$s and at most $k_2$ $1$s is the coefficient of $[u^xw^y]$ in $G(u,w)$ with
\begin{align*}
[u^xw^y]G(u,w)&=[u^xw^y]\frac{H_{k_1+1}(u)H_{k_2+1}(w)}{1-uwH_{k_1}(u)H_{k_2}(w)}\tag{5}\\
&=[u^xw^y]{H_{k_1+1}(u)H_{k_2+1}(w)}\\
&\qquad\qquad\cdot\sum_{n\geq 0}(uw)^n\left(H_{k_1}(u)\right)^n\left(H_{k_2}(w)\right)^n
\end{align*}
The coefficients $[u^x]$ and $[w^y]$ can be calculated separately due to the (relatively) nice structure of $G(u,w)$. We find
\begin{align*}
[u^x]u^n\left(H_{k_1}(u)\right)^n&=[u^x]u^n\left(\frac{1-u^{k_1}}{1-u}\right)^n\\
&=[u^{x-n}]\sum_{j=0}^{n}\binom{n}{j}(-u)^{k_1j}\sum_{l\geq 0}\binom{-n}{l}(-u)^l\\
&=[u^{x-n}]\sum_{j=0}^{n}\binom{n}{j}(-u)^{k_1j}\sum_{l\geq 0}\binom{n+l-1}{l}u^l\\
&=\sum_{l\geq 0}\binom{n+l-1}{l}[u^{x-n-l}]\sum_{j=0}^{n}\binom{n}{j}(-u)^{k_1j}\\
&=\sum_{j=0}^{n}(-1)^{k_1j}\binom{n}{j}\binom{n+(x-n-k_1j)-1}{x-n-k_1j}\\
&=\sum_{j=0}^{n}(-1)^{k_1j}\binom{n}{j}\binom{x-k_1j-1}{n-1}
\end{align*}
Similar calculations can be used to find the other parts of (5).
Simplification: If we consider the simplified problem of counting the number of runs of length at most $k$ in a binary alphabet, we can use a univariate generating function based upon (3) and (4).
- The symbolic equation (3) simplifies to
\begin{align*}
\text{SEQ}^{\leq k}(1)\text{SEQ}\left(0\text{SEQ}^{\leq k-1}(0)1\text{SEQ}^{\leq k-1}(1)\right)\text{SEQ}^{\leq k}(0)
\end{align*}
- and instead of $G(u,w)$ in (4) we can write:
\begin{align*}
\widetilde{G}(u)&=\frac{\left(\frac{1-u^{k+1}}{1-u}\right)^2}{1-\left(u\frac{1-u^{k}}{1-u}\right)^2}\\
&=\frac{1-u^{k+1}}{1-2u+u^{k+1}}\\
\end{align*}
Reference: The generating function $\widetilde{G}(u)$ is Example 1.10 in Analytic Combinatorics the classic from P. Flajolet and R. Sedgewick. The symbolic method is described there in section I.1 and I.2.
Best Answer
For part c), we can think of 01010101 as another string S. Because we cannot have S appear twice, we are looking for all binary strings of length 3 with one S. Then, we simply have $3\cdot2^2$ possible strings because for each of the 3 positions of S there are $2^2$ other binary strings of length 2.
The only case where it overcounts is (I believe) S01 = 01S. All binary strings xSx is different from Sxx and xxS because the third element of xSx must be a 0 while the third element of the latter two must be a 1. But for the latter two to the the same, S01 = 01S (because the first, second, second last and last characters must be 01 to match S) and therefore we have only overcounted once.
Hence our final answer is $3\cdot2^2 - 1$.