I have already mentioned in a comment that the condition $N_w(k)=p_k$ cannot be satisfied for all $k$, otherwise we would have $p_{k+1}−p_k\leq 2(p_k−p_{k−1})$ which is not the case (should I explain the necessity of this condition?). Moreover, it *should* be at least true that there are infinitely many $k$ violating this inequality.

On the other hand, the required growth rate is possible.

Let us start with a general construction. Assume that $a_1,a_2,\dots$ is an increasing sequence such that the sequence $d_i=a_{i+1}-a_i$ is also strictly increasing. Let $w$ be the word where ones are placed exactly on the positions numbered by the $a_i$.

Take any $n$; find the largest $k$ with $d_k<n-1$. Then each of the first $a_k$ subwords of length $n$ contains at least two ones and hence its position in $w$ is uniquely determined by the gap between these ones. All the next $n$-subwords contain at most one 1, and there are $n+1$ of them. Thus $N_w(n)=a_k+n+1$. Notice here that if the monotonicity arises only eventually, this changes $N_w(n)$ by at most a constant, thus it does not affect its grpwth rate.

Now we need to specify this construction in order to get $N_w(n)\sim n\ln n$. Set $a_k=[e^{\sqrt{2k}}]$; Then the sequences $(a_k)$ and $(d_k)$ are eventually monotone, and $d_{k+1}/d_k\to 1$ as $k\to \infty$. Next,
$$
d_k=a_{k+1}-a_k\sim e^{\sqrt{2k}}(e^{\sqrt{2(k+1)}-\sqrt{2k}}-1)
\sim \frac{e^{\sqrt{2k}}}{\sqrt{2k}}\sim \frac{a_k}{\sqrt{2k}}.
$$
Thus
$$
N_w(d_k+2)=a_k+d_k+3\sim a_k\sim d_k\sqrt{2k}\sim d_k\ln d_k;
$$
due to the monotonicity of $N_w$ and the fact that $d_{k+1}/d_k\to 1$, we obtain $N_w(n)\sim n\ln n$, as required.

**REMARKS.** How to find this strange form of $a_k$? Setting $a_k=e^{f(k)}$, we obtain that we need $f(k)(e^{f(k+1)-f(k)}-1)\sim 1$. Replacing $f(k+1)-f(k)$ by $f'(k)$, we get $e^{f'}-1=1/f$, or $f'=\ln(1+1/f)\sim 1/f$. Thus $f(k)\sim \sqrt{2k}$.

We have used the properties that $d_k$ increases, that $d_k=o(a_k)$ (in the last estimate), and that $d_{k+1}/d_k\to 1$. This shows the conditions within which this method works.