Challenge: K Consecutive Ones

What if we allow up to $k-1$ consecutive 1s, but not $k$ or more? Track the last $k-1$ digits, not just the last one. State: $(pos, tight, lastKDigits)$ where $lastKDigits$ is a bitmask of the last $k-1$ positions. Transition: shift the mask left, add new digit, check if all $k$ digits are 1 (invalid). For $k = 3$ in base 10: track last 2 digits. State space: $O(\log N \cdot 2 \cdot 10^{k-1})$. Gets expensive for large $k$.

Time complexity: $O(\log N \cdot 2 \cdot 10^{k-1})$. Space complexity: $O(\log N \cdot 2 \cdot 10^{k-1})$ for the dp table.